1
BAB VII PENCARIAN DATA (SEARCHING)
Seperti halnya dengan pengurutan data, pencarian data (searching) merupakan operasi yang penting dalam pengolahan data. Bahkan, tidak jarang keduanya digunakan secara bersama-sama untuk menghasilkan output yang sesuai kebutuhan para pemakai. Pembahasan pada bagian ini akan meninjau tentang dua macam metoda yang dapat diterapkan dalam permasalahan pencarian data, yaitu metoda pencarian langsung (linear search) dan metoda pencarian biner (binary search).
Umumnya, metoda pencarian langsung akan lebih efisien digunakan untuk mencari data dalam sekelompok data dalam jumlah data yang sedikit. Dalam kondisi data yang hendak dicari berada dalam sekumpulan data yang tidak urut, maka penerapan metoda pencarian langsung akan lebih mudah. Sekalipun demikian, dalam cacah data yang banyak maka penerapan metoda ini akan mengakibatkan proses yang tidak efisien. Dalam kasus demikian, mungkin akan menjadi lebih baik jika data diurutkan terlebih dahulu dan kemudian pencarian dilakukan menggunakan metoda pencarian biner. Sebaliknya, dalam kondisi dimana data yang akan dicari berada dalam sekelompok data dalam jumlah yang besar dan urut, maka penggunaan metoda pencarian biner akan memberikan hasil yang lebih efisien.
7.1.
Metoda Pencarian Langsung (Linear Search)
Proses pencarian data dengan metoda pencarian langsung cukup sederhana dan mudah dipahami. Dalam metoda ini proses pencarian dilakukan dengan cara mencocokkan data yang akan dicari dengan semua data yang ada dalam kelompok data. Proses pencocokan data dilakukan secara berurutan satu demi satu dimulai dari data ke-1 hingga data pada urutan terakhir. Jika data yang dicari mempunyai harga yang sama dengan data yang ada dalam kelompok data, berarti data telah ditemukan. Tetapi jika data yang dicari tidak ada yang
2
cocok dengan data-data dalam kelompok data, berarti data tersebut tidak ada dalam kelompok data. Selanjutnya kita tinggal menampilkan hasil yang diperoleh tersebut.
Secara lebih terinci, proses pencarian data dengan metoda pencarian langsung adalah dijelaskan sebagai berikut. Jika X menyatakan data yang akan dicari, dan K adalah vektor tempat data akan dicari dan memuat N buah data. Dengan menggunakan proses perulangan, maka pencarian data X dalam K adalah dilakukan dengan cara membandingkan harga X dengan setiap harga pada vektor K dimulai pada K[1], kemudian K[2], K[3], dan seterusnya hingga K[N]. Jika X mempunyai harga yang sama dengan harga K[I], berarti X ditemukan pada K. Langkah selanjutnya adalah mencetak hasil tersebut. Proses demikian akan dilakukan terus menerus hingga K[N].
Jika data X tidak pernah cocok
dengan harga K[I] hingga data K[N], berarti data X tidak ditemukan dalam vektor K dan selanjutnya ditampilkan pesan bahwa data yang dicari tidak ditemukan.
Berikut ini contoh penerapannya, diketahui vektor K yang memiliki elemen data, sebagai berikut : 20
22
18
15
26
34
43
25
Data yang akan dicari adalah 34 (X=34). Untuk mencari data tersebut, mula-mula 34 akan dibandingkan dengan data pertama, yaitu 20. Karena tidak sama, maka langkah selanjutnya akan dibandingkan dengan 22, kemudian dengan 18, 15, 26, dan 34. Pada langkah ke-6 ini data 34 telah ditemukan. Proses perbandingan akan terus dilakukan hingga data pada urutan terakhir.
Flowchart prosedur untuk pencarian data dengan metoda pencarian langsung adalah ditunjukkan pada Gambar 7.1. Sedangakn solusi bentuk algoritma prosedur untuk pencarian data dengan metoda pencarian langsung dapat dituliskan sebagai berikut ini.
Dari vektor K dengan N buah elemen data. Data yang dicari dibaca sebagai X. 1. Mulai
3
2. Proses berulang langkah-3 FOR I = 1 TO N 3. Pencarian data IF K[I] = X Jika ya, data ketemu dan cetak hasil (“Data “,X,” ada pada urutan ke : “,I) 4. Data tidak ditemukan dan cetak pesan. (“Data “,X,” tidak ditemukan dalam vektor”) 5. Selesai
Mulai Baca Vektor K, X FOR I = 1 TO N YA
X=K[I]
TIDAK
“Data “,X,” ada pada urutan ke : “,I
NEXT I
“Data “,X,” tidak ditemukan dalam vektor”
Selesai
Gambar 7.1 : Flowchart prosedur pencarian data dengan metoda pencarian
Dalam algoritma di atas, jika data yang dicari muncul beberapa kali dalam kelompok data, maka setiap kali ditemukan akan ditampilkan pesan tentang posisinya dalam kelompok data. Jika ada sepuluh data yang sama, maka posisi sepuluh data yang cocok tersebut akan dicetak semuanya secara berurutan. Sekalipun demikian, proses pencarian akan tetap dilakukan sampai data terakhir. Jika data yang dicari tidak pernah ditemukan hingga data terakhir, maka akan dicetak pesan bahwa data yang dicari tidak ditemukan dalam vektor K.
4
Dalam kondisi dimana harga data dalam vektor tidak pernah sama, maka proses pencarian akan dihentikan jika data yang dicari telah ditemukan. Dengan demikian, maka algoritma di atas perlu dimodifikasi (modifikasi 1). Algoritma untuk hal ini dapat dituliskan seperti di bawah ini. Sedangkan flowchart prosedurnya ditunjukkan pada Gambar 7.2.
Dari vektor K dengan N buah elemen data yang berbeda Data yang dicari dibaca sebagai X. 1. Mulai 2. Proses berulang langkah-3 FOR I = 1 TO N 3. Pencarian data IF K[I} = X Jika ya, data ketemu dan cetak hasil (“Data “,X,” ada pada urutan ke : “,I) Ke langkah-5 4. Data tidak ditemukan dan cetak pesan (“Data “,X,” tidak ditemukan dalam vektor”) 5. Selesai
Mulai Baca Vektor K, X FOR I = 1 TO N YA
TIDAK
X=K[I]
NEXT I
“Data “,X,” ada pada urutan ke :
“Data “,X,” tidak ditemukan dalam vektor” Selesai Gambar 7.2 : Flowchart prosedur pencarian data dengan metoda pencarian langsung (modifikasi 1)
5
Jika saja data yang dicari tidak ditemukan dalam vektor dan kemudian data tersebut akan ditambahkan sehingga akan terbentuk suatu vektor baru, maka algoritma di atas perlu dimodifikasi kembali (modifikasi 2). Seandainya data yang tidak ditemukan tersebut akan ditambahkan pada urutan terakhir, maka solusi dalam bentuk algoritmanya adalah dituliskan di bawah ini dan Gambar 7.3 menunjukkan flowchart prosedurnya.
Dari vektor K dengan N buah elemen data Data yang dicari dibaca sebagai X, jika tidak ditemukan ditambahkan pada urutan terakhir. 1. Mulai 2. Proses berulang langkah-3 FOR I = 1 TO N 3. Pencarian data IF K[I] = X Jika ya, data ditemukan dan cetak hasil (“Data “,X,” ada pada urutan ke : “,I) 4. Data tidak ditemukan dan akan ditambahkan pada urutan terakhir N+N+1 K{N} = X Cetak pesan (“Data “,X,” tidak ditemukan dalam vektor dan ditambahkan pada posisi ke : ’,N) 5. Selesai
6
Mulai Baca Vektor K, X
FOR I = 1 TO N YA
X=K[I]
TIDAK
“Data “,X,” ada pada urutan ke : “,I
NEXT I “Data “,X,” tidak ditemukan dalam vektor dan ditambahkan pada posisi ke : “,N
Selesai
Gambar 7.3 : Flowchart prosedur pencarian data dengan metoda pencarian langsung (modifikasi 2) Metoda pencarian langsung dapat diterapkan pada semua kondisi permasalahan pencarian data. Namun demikian, umumnya metoda ini paling baik digunakan jika cacah data dalam vektor relatif sedikit. Sebaliknya, dalam kondisi cacah data yang cukup besar dan data dalam vektor telah berada dalam kondisi urut, maka penggunaan metoda pencarian langsung menjadi tidak efisien lagi. Hal ini dikarenakan proses yang dilakukan harus membandingkan dengan hampir semua
data
dalam
vektor.
Sayangnya
jarang
sekali
kita
menemukan
keberuntungan seperti ini. Dalam kondisi yang demikian, maka penggunaan metoda pencarian langsung selalu dihindari dan sebagai gantinya adalah digunakan metoda pencarian biner.
7
7.2. Metoda Pencarian Biner (Binary Search)
Pembahasan berikut ini dibatasi pada pencarian data pada vektor urut naik dimana harga elemen-elemennya tidak ada yang sama. Pencarian data dengan metoda pencariab biner pada vektor tersebut dapat dijelaskan sebagai berikut ini. Jika vektor memuat N buah elemen data, maka mula-mula kita tetapkan harga batas bawah dan batas atas interval. Dari dua harga tersebut kemudian dapat ditentukan titik tengah intervalnya. Misal harga batas bawah interval bawah dinyatakan dengan variael BAWAH, harga batas atas interval dinyatakan dengan variabel ATAS, dan titik tengah interval dinyatakan dengan vareiabel TENGAH. Dengan demikian, maka harga awal untuk BAWAH adalah sama dengan 1 dan ATAS adalah sama dengan N. Sedangkan TENGAH dihitung dengan cara sebagai berikut :
TENGAH = (ATAS + BAWAH) DIV 2
Jika cacah data dalam vektor adalah ganjil, maka titik tengah interval akan membagi vektor tersebut menjadi dua bagian yang persis sama. Sebaliknya, jika cacah data dalam vektor adalah genap, maka titik tengah interval akan membagi vektor menjadi dua bagian dimana salah satu bagian akan mempunyai cacah data lebih banyak.
Data-data yang mempunyai harga lebih kecil dari harga data pada titik tengah interval akan berada di sebelah kiri titik tengah interval dan data-data yang mempunyai harga lebih besar dari harga data pada titik tengah interval akan berada di sebelah kanan titik tengah interval. Data yang dicari, kemudian dibandingkan dan dicocokkan dengan data pada posisi TENGAH. Jika sama, maka data telah ditemukan dan proses selesai. Namun, jika data yangdicari lebih kecil dari harga data pada posisi TENGAH, berarti data yang dicari berada dalam interval di sebelah kiri. Selanjutnya, proses pencarian hanya akan difokuskan pada interval tersebut dan kita tidak perlu lagi membandingkan dengan data-data pada interval kanan. Untuk itu harga ATAS perlu digeser menjadi TENGAH – 1.
8
Sebaliknya, jika elemen data yang dicari mempunyai harga lebih besar dari harga pada posisi TENGAH, berarti data yang dicari adalah berada di interval sebelah kanan. Selanjutnya proses pencarian hanya akan difokuskan pad interval tersebut. Harga BAWAH kemudian dinaikkan menjadi TENGAH + 1.
Selanjutnya harga TENGAH akan ditentukan kembali berdasarkan harga BAWAH dan ATAS yang baru pada interval dimana data yang dicari berada. Perhitungannya dilakukan sebagaimana formula di atas. Perbandingan dan pencocokan antara data yang dicari dengan data pada posisi TENGAH akan dilakukan
kembali.
Dengan
demikian
akan
terjadi
tiga
kemungkinan
sebagaimana sebelumnya, yaitu data yang dicari mempunyai harga sama dengan harga data pada posisi TENGAH, lebih kecil, atau lebih besar. Pergeseran harga BAWAH dan ATAS akan dilakukan kembali berdasarkan harga-harga batas interval yang baru tersebut.
Proses seperti ini akan dilakukan secara terus menerus selama harga BAWAH kurang dari atau sama dengan harga ATAS. Pada akhirnya, jika data yang dicari memang berada dalam vektor maka data tersebut akan dapat ditemukan, yaitu ketika data yang dicari mempunyai harga yang sama dengan harga data pada posisi TENGAH. Sebaliknya, apabila harga BAWAH telah sama dengan harga ATAS tetapi data yang dicari tidak pernah sama dengan harga data pada posisi TENGAH, berarti data tersebut tidak ada dalam vektor. Dengan demikian, maka proses pencarian dapat dihentikan. Dengan cara seperti ini, maka proses pencarian data dapat dilakukan dengan lebih cepat, karena proses perbandingan dan pencocokan data tidak harus dilakukan pada semua elemen data. Pencarian dengan metoda pencarian biner akan memerlukan proses tambahan untuk perhitungan batas-batas interval, namun demikian, dalam cacah data yang cukup banyak, proses tambahan tersebut tetaplah lebih efisien dibandingkan jika harus melakukan perbandingan dan pencocokan satu per satu pada semua eleman data dalam vektor sebagaimana dalam metoda pencarian langsung.
9
Mulai Baca Vektor K, X ATAS = N BAWAH = 1
YA
TIDAK
WHILE ATAS <= BAWAH
TENGAH = (ATAS + BAWAH) DIV 2 YA
TIDAK X=K[TENGAH] YA
“Data “,X,” ada pada urutan ke : “,TENGAH
X
ATAS = TENGAH + 1
TIDAK
ATAS = TENGAH + 1
“Data “,X,” tidak ditemukan dalam vektor”
Selesai Gambar 7.4 : Flowchart prosedur pencarian data dengan metoda pencarian biner
Berikut ini dituliskan solusi dalam bentuk algoritma pencarian data dengan metoda biner. Sedangkan flowchart prosedurnya ditunjukkan pada Gambar 7.4.
Dari vektor K dengan N buah elemen data. Data yang dicari dibaca sebagai X. 1. Inisialisasikan ATAS = N BAWAH = 1 2. Proses berulang langkah-3 s/d langkah-4 WHILE BAWAH <= ATAS 3. Hitung harga titik tengah intervalnya
10
TENGAH = (BAWAH + ATAS) DIV 2 4. Bandingkan harga data yang dicari dengan harga tengah interval IF X = K[TENGAH] Jika ya, data ketemu dan cetak hasil (“Data “,X,” ada pada urutan ke : “,TENGAH) Ke langkah-6 Jika tidak, cetak lokasi data IF X < K[TENGAH] Jika ya, tentukan batas atas interval baru ATAS = TENGAH – 1 Jika tidak, tentukan batas bawah interval baru BAWAH = TENGAH + 1 5. Data tidak ketemu dan cetak pesan (“Data “,X,” tidak ditemukan dalam vektor” 6. Selesai
Berikut juga akan diberikan contoh penerapan metoda pencarian biner dalam pencarian data. Jika diketahui sebuah vektor K yang mempunyai tujuh elemen data numerik, yaitu sebagai berikut :
27
30
32
46
48
49
55
Berdasarkan data-data dalam vektor K, maka akan dicari elemen data yang mempunyai harga 32. Penentuan lokasi titik tengah interval pada setiap langkah untuk membandingkan harga data yang dicari dengan harga data pada lokasi titik tengah interval tersebut ditunjukkan pada Tabel 7.1.
Sedangkan Tabel 7.2. menunjukan penentuan lokasi titik tengah interval pada pencarian data 55 dalam vektor K. Dalam kedua tabel tersebut, harga data yang dicari akan selalu dibandingkan dengan harga data pada lokasi titik tengah interval yang diperoleh. Jika keduanya mempunyai harga yang sama, berarti data telah ditemukan dan tinggal mencetak hasilnya untuk kemudian proses dapat dihentikan. Jika tidak sama, maka proses akan diulang kembali untuk
11
menentukan titik tengah interval yang baru sampai harga ATAS sama dengan harga BAWAH, sehingga titik tengah intervalnya juga akan sama.
Dalam contoh pertama, data 32 mempunyai posisi aktual pada urutan ke-3. Data tersebut jika dicari menggunakan metoda pencarian langsung akan ditemukan pada langkah iterasi ke-3. Demikian juga jika diselesaikan dengan metoda pencarian biner juga akan ditemukan pada langkah iterasi ke-3. Dalam contoh kedua, data 55 mempunyai posisi aktual pada urutan ke-7. Jika menggunakan metoda pencarian langsung, maka data tersebut baru akan ditemukan pada langkah ke-7. Tetapi jika menggunakan metoda pencarian biner akan ditemukan pada langkah iterasi ke-3.
Tabel 7.1: Contoh pencarian data dengan metoda pencarian biner (Contoh 1) Iterasi ke :
BAWAH
ATAS
TENGAH
K[TENGAH]
1
1
7
4
46
2
1
3
2
30
3
3
3
3
32
Tabel 7.2: Contoh pencarian data dengan metoda pencarian biner (Contoh 2) Iterasi ke :
BAWAH
ATAS
TENGAH
1.00
1.00
7.00
4.00
2.00
5.00
7.00
6.00
3.00
7.00
7.00
7.00
Berdasarkan kedua contoh sederhana tersebut, kita dapat membandingkan efisiensi masing-masing metoda pencarian langsung dan pencarian biner jika diterapkan dalam program-program aplikasi. Secara umum, faktor utama yang menentukan dalam pemilihan metoda pencarian data adalah kondisi data dan cacah data. Dalam kondisi dimana data dalam vektor belum diurutkan, maka pencarian data tidak mungkin dilakukan dengan metoda pencarian langsung. Namun jika cacah datanya cukup besar, maka akan lebih baik jika kita bisa menerapkan metoda pencarian biner, dengan syarat harus mengurutkan datanya
12
terlebih dahulu. Cara demikian lazim dilakukan dalam suatu sistem pengolahan data, karena kenyataannya pengolahan data akan selalu melibatkan sejumlah data yang besar. Sehingga operasi pengurutan yang harus dilakukan tersebut tidak selalu merugikan.
Sebaliknya jika data dalam telah diurutkan, maka kita dapat menggunakan metoda pencarian langsung atau metoda pencarian biner. Permasalahanya tinggal tergantung pada cacah datanya. Jika cacah datanya sedikit, maka penggunaan metoda pencarian langsung akan lebih efisien. Namun dalam cacah data yang besar, maka penggunaan metoda pencarian biner akan jauh lebih menguntungkan dan efisien.
