Binary Search Klasik Tanpa Bug

Pencarian biner menemukan nilai dalam daftar terurut dengan membagi dua rentang pada setiap langkah. Dengan begitu, pemindaian lambat O(n) berubah menjadi pencarian cepat O(log n).

Pencarian biner hanya bekerja pada data yang terurut. Jika daftar tidak berurutan, urutkan terlebih dahulu; jika tidak, hasilnya tidak bermakna dan salah.

Mulailah dengan dua penunjuk: low pada indeks 0 dan high pada indeks terakhir. Jika ada, target selalu berada di antara keduanya.

Hitung mid sebagai low + (high - low) // 2. Dalam Python, overflow bukan masalah, tetapi bentuk ini merupakan kebiasaan aman di mana pun.

Bandingkan a[mid] dengan target. Anda mungkin menemukannya, nilainya terlalu kecil, atau terlalu besar. Setiap kasus mempersempit rentang dengan cara yang berbeda.

Jika a[mid] lebih kecil daripada target, jawaban pasti berada di sebelah kanan. Pindahkan low ke mid + 1 dan buang separuh kiri.

Jika a[mid] lebih besar daripada target, cari di separuh kiri. Pindahkan high ke mid - 1 agar mid tidak pernah diperiksa lagi.

Lanjutkan selama low kurang dari atau sama dengan high. Saat keduanya saling melewati, rentangnya kosong dan target tidak ada.

Jika perulangan berakhir tanpa kecocokan, nilainya tidak ada. Kembalikan -1 sebagai konvensi agar pemanggil dapat membedakan keberhasilan dan kegagalan.

Kesalahan klasiknya adalah melupakan +1 atau -1 saat memindahkan penunjuk. Jika dilewati, mid akan diuji ulang selamanya dan menyebabkan perulangan tak berujung.

Untuk pengujian keanggotaan biasa, modul Python bisect sudah menyediakan pencarian bebas kesalahan. Tulis perulangan sendiri hanya jika Anda memerlukan logika khusus.

Pikirkan hal yang menjaga perulangan tetap benar.

Sekarang Anda dapat menetapkan low dan high, menghitung mid dengan aman, mempersempit sisi yang tepat, dan menghindari jebakan selisih satu. Pencarian logaritmik kini dapat Anda gunakan. 🎯