Pencarian biner
Menemukan nilai dalam larik terurut dengan melihat bagian tengah dan membuang separuh tempat nilai itu tidak mungkin ada. Setiap perbandingan membagi dua sisanya.
- terbaik Ω(1)
- rata-rata Θ(log n)
- terburuk O(log n)
- memori O(1)
Apa artinya?
- Terurut: dalam urutan naik. Pencarian biner membutuhkannya; pada data tak terurut hasilnya salah.
- Membagi dua: setiap perbandingan membuang separuh sisanya, separuh tempat target tidak mungkin ada.
- log₂ n: berapa kali n bisa dibagi dua sampai tersisa 1. Untuk 64 nilai hasilnya 6, jadi paling banyak 7 perbandingan.
- tengah (mid)
- ditemukan
- disingkirkan
- target
Setiap tengah yang bisa dipilih pencarian; satu jalannya adalah satu jalur ke bawah. Tingkat: 5 = ⌈log₂(24 + 1)⌉, perbandingan terbanyak yang mungkin diperlukan.
Mencari 70 di antara 24 nilai terurut: seluruh larik masih dalam permainan.
Spasi: putar atau jeda. Panah kiri dan kanan: melangkah. Home dan End: lompat.
Coba ini: Pilih target yang tidak ada di larik. Pencarian tetap berhenti setelah paling banyak ⌈log₂(n + 1)⌉ perbandingan, saat lo melewati hi.
Cara kerjanya
Pencarian biner memegang dua penanda, lo dan hi, di sekitar bagian larik tempat target masih mungkin berada. Ia melihat nilai di tengah: jika itu targetnya, selesai; jika lebih kecil, target hanya bisa di kanan, jadi lo pindah melewati tengah; jika lebih besar, hi pindah ke depannya. Setiap langkah membagi dua sisanya: 64 nilai butuh paling banyak 7 perbandingan, sejuta paling banyak 20. Saat lo melewati hi, tidak ada yang tersisa: nilai itu tidak ada di larik.
Kapan ini pilihan yang tepat
Gunakan pencarian biner setiap kali data terurut dan Anda bisa melompat ke posisi mana pun: kata dalam daftar terurut, versi dalam riwayat rilis, git bisect, tempat menyisipkan ke larik terurut. Pada data tak terurut hasilnya salah, dan mengurutkan dulu hanya sepadan jika Anda mencari berkali-kali.