Halo!!! Kembali lagi. Kali ini saya akan berbagi ilmu tentang binary search. Nah apa sih binary search? Langsung saja simak di bawah ini.
Apa sih binary search? Binary search adalah salah satu metode pencarian yang bisa dibilang tercepat dari metode - metode pencarian lainnya. Kok bisa tercepat sih? karena dalam metode pencarian yang satu ini, data yang dicarinya sudah terurut. Begitulah mengapa binary search bisa menjadi yang tercepat kalau dibandingkan dengan metode pencarian lainnya. Sebenarnya dalam kehidupan siswa atau mahasiswa kita pasti pernah mencari arti kata bahasa inggris di kamus, nah untuk mencarinya kita tidak membuka kamus tersebut dari halaman pertama hingga halaman yang dicari atau dengan kata lain membuka halamannya satu per satu, tetapi kita mencari di bagian tengah jika kata yang dicari tidak ketemu kita dapat melanjutkan pencarian di bagian sebelah kiri ataupun di bagian sebelah kanan sampai kata yang dicari ketemu.
Masih bingung? kalo jawabannya "Iya" bisa langsung di simak lagi penjelasan dan ilustrasi di bawah ini.
Misalkan data yang kita miliki adalah sebagai berikut :
Dari data tersebut, kita misalkan indeks kiri itu dengan variabel "i" dan yang kanan dengan "j". Lalu kita inisialisasi i =1 dan j = n. Untuk data yang kita punya, kita isi j dengan 8. Dan cara selanjutnya :
- Bagi dua larik atau array dengan cara k = (i + j) / 2.
- Cek apakah L[k] = x atau data yang dicari. Jika sama, pencarian data pun selesai. Jika tidak harus ditentukan apakah pencarian akan dilanjutkan ke larik sebelah kiri atau kanan dengan cara, jika L[k] < x, maka pencarian dilanjutkan di bagian kiri, begitupun sebaliknya.
- Ulangi lagi langkah 1 sampai x ditemukan atau jika i > j dengan kata lain ukuran larik sudah nol.
Langsung pada ilustrasi saja, dari data yang kita punya kita akan mencari x = 15.
Langkah pertama :
i = 1, j = 8 dan k = (1 + 8) / 2 = 4.5. Karena hasilnya 4.5, kita bisa memilih k = 4 atau k = 5. Tetapi kita untuk kasus ini kita akan memilik k = 4.
Lalu, cek apakah L[4] = 15? Tidak sama kan? berarti lanjut lagi ke langkah berikutnya, yaitu bandingkan apakah L[4] > 15? Lebih besar kan? artinya kita lanjutkan pencarian ke larik sebelah kanan dengan i = k + 1 dan j = 8.
Jika sudah, kita ulangi lagi langkah pertama, yaitu :
kita bagi dua lagi dengan cara yang sama seperti sebelumnya. Dibawah adalah hasilnya :
Langkah selanjutnya adalah bandingkan apa L[6] = 15? Tidak sama lagi kan? berarti lanjut lagi ke langkah selanjutnya dengan membandingkan lagi L[6] > 15? Lebih kecil kan? artinya lagi kita harus lanjutkan pencarian ke sebelah kiri dengan i = 5 dan j = k - 1 = 5.
Ini masih belum hasil akhirnya. Loh? Kok masih belum hasil akhirnya? Jawabannya kan sudah ketemu?. Sabar yah, komputer dan manusia itu berbeda. Walaupun jawabannya sudah di depan mata tetapi jika proses pencariannya belum selesai prosesnya masih tetap lanjut.
Oke, untuk langkah berikutnya adalah sama kita bagi dua lagi lariknya dengan i = 5 dan j = 5 juga. k = (5 + 5) / 2 = 5.
Berikutnya adalah bandingkan L[5] = 15? Jawabannya "Iya" kan? karena data yang dicari sudah ditemukan maka proses pencarian pun selesai.
Adapun algoritma pencariannya juga.
Terima kasih sudah meluangkan waktunya dan kalo ada yang mau ditanyakan silahkan beri komentar di postingan ini yah.
Sumber :
Munir, Rinaldi. 2011. Algoritma & Pemograman Dalam Bahasa Pascal dan C Edisi Revisi. Bandung : Informatika Bandung.
https://en.wikipedia.org/wiki/Binary_search_algorithm
http://allaboutalgoritma.blogspot.co.id/2009/06/binary-search.html
EmoticonEmoticon