Algoritma Binary Search Dengan Recursive

Pernahkah kalian memiliki kamus Bahasa Inggris? Saya yakin hampir semuanya punya! Bayangkan kalian akan mencari kata “melon” dalam kamus tersebut, tetapi kamusnya tidak memiliki indeks huruf yang ada di sisinya seperti gambar berikut, apa yang akan kalian lakukan?

Metode Pencarian

Saya rasa ada dua cara untuk mencari kata “melon” dalam kamus tersebut.

Pertama, kalian membukanya dari lembar pertama sedikit demi sedikit. Ini akan sangat melelahkan karena huruf “M” pasti ada berada di tengah kamus.

Kedua, kalian membukanya langsung dari tengah. Kemudian jika yang ditemukan huruf “N”, maka akan bergeser ke kiri. Jika yang ditemukan huruf “L”, maka akan bergeser ke kanan. Cara ini tentunya lebih efektif daripada cara pertama.

Tahukah kalian? Bahwa rata-rata pemikiran programmer pemula adalah di cara pertama? Kok bisa? Karena mereka merasa dengan mudah melakukan pencarian dengan for saja. Misalnya mereka diperintahkan mencari angka 4 dalam array [1, 2, 3, 4, 5, 6, 7, 8]. Maka mereka akan menulis kode seperti ini:

Kodenya tidak salah, fungsi tersebut akan mengembalikan data yang benar. Namun cara tersebut tidaklah efektif seperti mencari kata “melon” dalam kamus dengan cara pertama. Cara tersebut adalah linear search, dimana kita akan melakukan looping satu persatu kemudian akan berhenti ketika angka yang dicari ditemukan. Bayangkan jika array-nya berisi 1000 item ternyata angka yang dicari adalah 999, maka kompleksitas waktu yang dibutuhkan adalah 999x! Tidak efektif bukan?

Cara Kerja Binary Search

Sesuai dengan namanya, binary adalah antara 1 dan 0 atau ya dan tidak. Maka dari itu, algoritma ini hanya mengandalkan jika tidak yang kanan, maka yang kiri, dan begitu seterusnya sampai akhirnya angka yang dicari ditemukan. Mari kita pelajari!

Misalnya kita akan mencari angka 800 dari array [1, 2, 3, …. 1000]. Kita akan membuat dua variabel, yaitu start dan end.

Pertama, kita akan mengambil nilai yang ada di tengah, caranya adalah (start + end) / 2 = (0 + 1000) / 2 maka yang dihasilkan adalah 500.

Kedua, karena 500 lebih kecil dari 800, maka kita akan mengabaikan looping dari 0 ke 499 dan membuat angka tengah baru, yaitu start = 500 dan end = 1000. Maka 500 + 1000 / 2 = 750.

Ketiga, karena 750 masih lebih kecil dari 800, maka kita melakukan hal yang sama seperti cara pertama dan kedua. 750 + 1000 / 2 = 875.

Keempat, karena 875 lebih besar dari 800, maka kita melakukan hal yang sedikit berbeda, yaitu menggeser end ke angka ini, yaitu start = 750 dan end = 875. Maka 750 + 875 / 2 = 812.5. Karena binary search tidak menerima koma, maka akan kita bulatkan menjadi 812.

Kelima, karena 812 masih lebih besar, kita akan melakukan rumus pertama sampai keempat sampai akhirnya angka 800 ditemukan. Maka akan menjadi seperti ini:

750 + 812 / 2 = 781
781 + 812 / 2 = 796
796 + 812 / 2 = 804
796 + 804 / 2 = 800 // angka yang dicari

Jauh lebih simpel bukan? Mari kita ubah menjadi kode :

Perlu Diingat!

Contoh di atas seharusnya start adala 0 dan end adalah 999 karena pointer array dimulai dari 0. Namun untuk mempermudah pemahaman, dibulatkan menjadi 1000. Maka hasil indeks yang seharusnya adalah 799 bukan 800.