Pencarian biner

Pencarian biner adalah cara Anda mencari kata di kamus: buka di tengah, lihat apakah kata itu ada sebelum atau sesudahnya, lalu ulangi pada separuh itu. Pada daftar terurut, ia menemukan nilai apa pun di antara satu juta nilai dengan paling banyak 20 perbandingan.

Barisan batang yang terurut dengan batang tengah disorot, separuh barisan memudar, dan garis putus-putus pada ketinggian target
Barisan batang yang terurut dengan batang tengah disorot, separuh barisan memudar, dan garis putus-putus pada ketinggian target

Idenya

Dalam daftar terurut, satu perbandingan memberi tahu lebih dari sekadar apakah target ditemukan: ia memberi tahu di sisi mana target berada. Bandingkan target dengan nilai di tengah. Jika sama, selesai. Jika nilai tengah lebih kecil, semua nilai sebelumnya juga lebih kecil, jadi target hanya bisa ada setelahnya. Jika lebih besar, target hanya bisa ada sebelumnya. Simpan separuh itu saja dan ulangi.

Contoh

Cari 23 dalam 2, 5, 8, 12, 16, 23, 38, 56, 72, 91. Nilai tengahnya 16, lebih kecil, jadi tinggal 23 sampai 91. Nilai tengahnya 56, lebih besar, jadi tinggal 23 dan 38. Nilai tengahnya 23: ditemukan di tempat ke-6 setelah 3 perbandingan, sedangkan pencarian linear perlu 6. Mencari 40 dalam daftar yang sama membandingkan 16, 56, 23, dan 38, lalu tidak ada yang tersisa: 4 perbandingan untuk tahu bahwa 40 tidak ada, dibanding 10 untuk pencarian linear.

Dibagi dua, cepat menyusut

Setelah satu perbandingan tersisa paling banyak separuh daftar, setelah dua seperempat, setelah k paling banyak sekitar n/2ᵏ. Pencarian berhenti saat tidak ada yang tersisa, jadi butuh paling banyak ⌊log₂ n⌋ + 1 perbandingan: 6 untuk 40 nilai, 10 untuk 1.000, 20 untuk satu juta, dan 30 untuk satu miliar. Menggandakan daftar hanya menambah satu perbandingan. Ini ditulis O(log n).

Mudah dijelaskan, sulit dibuat benar

John Mauchly menjelaskan pencarian biner pada 1946, tetapi menurut Donald Knuth versi pertama yang benar untuk semua panjang daftar baru diterbitkan pada 1962. Jon Bentley kemudian mendapati bahwa hanya sekitar satu dari sepuluh programmer profesional yang menulisnya dengan benar: kondisi akhir dan plus atau minus satu saat membagi dua mudah salah. Pada 2006 Joshua Bloch menunjukkan bahwa cara umum mencari tengah, (low + high) / 2, bisa overflow untuk daftar yang sangat panjang, bug yang bertahun-tahun ada di pustaka Java. Menulis low + (high − low) / 2, seperti yang dilakukan aplikasi ini, menghindarinya.

John Mauchly (kelima dari kiri) bersama para pejabat ENIAC lainnya di depan ENIAC, dalam foto Angkatan Darat AS. Mauchly menjelaskan pencarian biner pada tahun 1946.
John Mauchly (kelima dari kiri) bersama para pejabat ENIAC lainnya di depan ENIAC, dalam foto Angkatan Darat AS. Mauchly menjelaskan pencarian biner pada tahun 1946.

Varian dan kegunaan

Jika ada duplikat, pencarian biner menemukan salah satu yang cocok; versi yang terus ke kiri atau ke kanan menemukan yang pertama atau terakhir, atau tempat nilai yang tidak ada akan disisipkan. Ide membagi dua yang sama dipakai untuk mencari akar persamaan (metode biseksi), versi tempat bug pertama kali muncul (git bisect), dan jawaban banyak teka-teki optimasi. Pohon pencarian biner menyimpan data sehingga setiap pencarian mengikuti jalur pembagian dua yang sama.

Jelajahi

Buka aplikasinya, pilih nilai di Cari, lalu tekan Langkah. Bagian yang diarsir adalah tempat target masih mungkin berada; nilai tengah disorot, dan separuh yang tersingkir memudar. Kotak-kotak menunjukkan berapa nilai yang masih mungkin dan berapa perbandingan yang dibutuhkan pencarian linear untuk nilai yang sama. Cari nilai yang tidak ada, atau gunakan 40 batang, untuk melihat selisihnya makin besar.

Pertanyaan yang sering diajukan

Berapa kompleksitas waktu pencarian biner?

O(log n): paling banyak ⌊log₂ n⌋ + 1 perbandingan untuk n nilai. Kasus terbaiknya satu perbandingan, saat target ada di tengah. Versi iteratif hanya butuh memori tambahan O(1).

Apa bedanya pencarian biner dan pencarian linear?

Pencarian linear memeriksa setiap nilai secara bergantian dan bisa dipakai pada daftar apa pun, tetapi bisa perlu n perbandingan. Pencarian biner hanya bisa dipakai pada daftar terurut, tetapi menyingkirkan separuh sisanya di setiap perbandingan, jadi hanya perlu sekitar log₂ n.

Apakah layak mengurutkan daftar hanya untuk memakai pencarian biner?

Hanya jika Anda mencarinya berkali-kali. Pengurutan butuh sekitar n log n langkah, lebih banyak dari satu pencarian linear. Setelah daftar terurut, setiap pencarian berikutnya sangat murah.

Bisakah pencarian biner dipakai selain pada daftar?

Bisa, pada apa saja yang bisa diuji untuk mengetahui di sisi mana jawabannya: rentang angka, versi-versi sebuah program, atau tebakan dalam permainan tebak lebih besar atau lebih kecil.

Siap mencobanya?

Buka PictorX di browser Anda — tanpa instalasi, tanpa kartu kredit untuk memulai.

Coba pencarian biner