Belajar Algoritma Binary Search

Hari ini saya pengen belajar tentang algoritma binary search, saya belajar dari buku Grokking Algorithm. Akan saya coba rangkum dan catat sesuai dengan bahasa saya sendiri yaa. Okee mari kita mulai.

Kasus

Misal kita perlu mencari seseorang di buku telepon. Nama nya berawalan dengan huruf K. Kita mulai mencari dari awal halaman dan terus membuka halamannya sampai kita menemukan nama yang berawalan dengan huruf K. Tapi sepertinya kita ndak kayak gitu yaa, pasti langsung cari di tengah karena kita tahu nama yang berawalan dengan huruf K pasti di bagian tengah buku telepon.

Atau misal kita mau mencari kata di kamus, dan kata nya berawalan dengan huruf O. Pasti sama yaa, kita mulai mencari nya di bagian tengah kamus.

Nah, kalau kita perlu melakukan pencarian seperti itu di pemrograman, kita bisa pakai algoritma binary search.

Binary search adalah sebuah algoritma. Inputnya adalah list elemen yang sudah diurutkan. Jika elemen yang kita cari ada di dalam list maka binary search akan mengembalikan nilai dari posisi elemen tersebut, jika tidak ada maka akan mengembalikan null.

Contohnya gini:

Begini cara kerja binary search. Misal saya memikirkan salah satu angka dari 1 sampai 100.

Kamu harus menebak angka yang saya pikirkan dengan percobaan yang sedikit mungkin, saya akan mengatakan kalau tebakanmu terlalu rendah, terlalu tinggi atau benar.

Misal kamu bakal menebak satu persatu 1, 2, 3, 4 .... dst.

Simple Search

Menebak dengan cara seperti itu namanya simple search. Dengan setiap tebakan, kamu hanya mengeliminasi satu angka. Jika angka yang saya maksud adalah 99, berarti kamu perlu menebaknya sampai 99.

Binary Search

Ada cara yang lebih baik untuk melakukan pencarian tersebut. Tebak saja angka nya langsung ke 50.

Jika terlalu rendah, kamu berhasil mengeliminasi setengah angka nya. Jadi kamu tahu kan 1-50 itu terlalu rendah. Selanjutnya tebak lagi ke 75.

Jika terlalu tinggi, kamu berhasil mengeliminasi sisa angkanya.

Nah dengan binary search, kamu selalu menebak angka nya dari tengah agar mengeliminasi sisa angka yang ada. Selanjutnya tebak saja 63 karena di tengah antara 50 - 75.

Nah inilah yang dinamakan binary search. Beginilah jumlah angka yang kamu eliminasi setiap kamu menebak.

Berapapun angka yang saya pikirkan, kamu bisa menebaknya maksimal dengan 7 tebakan saja, karena kamu mengeliminasi banyak angka di setiap tebakan.

Lalu misalnya kamu mau mencari kata di kamus. Kamus sendiri punya sekitar 240.000 kata. Hal terburuknya, berapa banyak langkah yang kamu perlukan untuk setiap pencarian kata?

Simple search perlu 240.000 langkah jika kata yang kamu cari berada di paling akhir kamus. Dengan binary search, setiap langkah pencarian akan mengeliminasi setengah dari jumlah kata sampai tersisa hanya satu kata yang kamu cari.

Jadi dengan binary search hanya perlu 18 langkah untuk mencari kata di kamus. Secara umum, untuk list dengan ukuran n, binary search akan membutuhkan log₂ n langkah pada kasus terburuk, sedangkan simple search akan membutuhkan n langkah.

Logaritma

Karena nantinya akan sering dipakai, kita perlu mengingat kembali apa itu logaritma. Mungkin kita lupa apa itu logaritma (atau saya aja? wkwk) tapi kita pasti tahu dong apa itu bilangan berpangkat atau eksponen. Jika ada log₁₀ 100, kita bacanya, "Berapa banyak perkalian untuk angka 10 agar hasilnya 100" Yak tul, jawabannya 2 karena 10 x 10 = 100. Jadi log₁₀ 100 = 2. Nah logaritma adalah kebalikan dari bilangan berpangkat.

Di buku yang saya pelajari, ketika membahas tentang waktu eksekusi dengan big O notation (yang akan saya bahas nanti), setiap log berarti dibaca log₂.

Ketika kamu ingin mencari sebuah elemen menggunakan simple search, hal terburuknya adalah kamu bisa saja mencari semua elemen satu persatu. Misal ada list dengan jumlah 8, kamu harus memeriksa nya 8 kali juga. Dengan binary search, kamu melakukan pengecekan dengan log n untuk kasus terburuknya. Untuk list dengan jumlah 8, jadi log 8 = 3, karena 2³ == 8. Maka kita hanya perlu melakukan pengecekan paling banyak 3 kali. Misal untuk list berjumlah 1.024, jadi log 1.024 = 10, karena 2¹⁰ == 1.024. Maka untuk list dengan jumlah 1.024 kamu hanya perlu mengecek paling banyak 10 kali.

Catatan

• Kalau masih bingung soal logaritma, kamu bisa belajar di Khan Academy.
• Binary Search hanya bisa dilakukan jika list yang ada sudah diurutkan. Contohnya, pada buku telepon namanya sudah urut secara alfabet a - z.

Implementasi

Mari kita coba implementasi binary search di Python. Contoh kodenya disini menggunakan array. Jika kamu ndak tahu array gapapa, nanti saya jelasin di tulisan selanjutnya. Yang harus kamu tahu adalah kamu bisa menyimpan sebuah urutan elemen dalam deretan wadah yang berurutan yang disebut array. Wadah-wadah ini diberi nomor mulai dari 0: wadah pertama ada di posisi 0, wadah kedua di posisi 1, wadah ketiga di posisi 2, dan seterusnya.

Kita akan buat fungsi yang namanya binary_search, yang mempunyai 2 parameter yaitu array yg sudah diurutkan dan sebuah item yang dicari. Jika itemnya ada di dalam array, fungsinya akan mengembalikan posisi item tersebut.

Kita perlu mencatat bagian array mana yang harus kita cari. Pertama, kita buat variabel dengan batas bawah nya adalah posisi awal dan batas atasnya adalah posisi akhir dari array:

low = 0
high = len(arr) - 1

Setiap iterasi, kita cek elemen yang paling tengah:

mid = (low + high) // 2
guess = arr[mid]

Jika terlalu rendah, kita tambah batas bawah atau low nya:

if guess < item:
  low = mid + 1

Jika terlalu tinggi, kita kurangi batas atas atau high nya. Kode lengkapnya jadi seperti ini:

Catatan

• Kode tersebut menggunakan python versi 3, kamu bisa coba sendiri menjalankan kodenya dan mengganti parameter yang dimasukkan ke dalam fungsinya dan lihat hasilnya agar lebih paham.
• Di buku dan tulisan saya menggunakan list dan array secara bergantian dalam kode. Karena di python, array disebut list.

dah gitu dulu yaa~