Binary Search — Algoritma, Kompleksitas Waktu & Kode

Binary search adalah cara cepat untuk menemukan target dalam daftar yang sudah diurutkan. Anda memeriksa item tengah, menyingkirkan setengah dari nilai yang tersisa, lalu mengulanginya. Jika daftar tidak terurut, logika itu tidak berlaku.

Pada daftar yang urut menaik, aturannya sederhana: jika nilai tengah lebih kecil daripada target, cari ke kanan; jika lebih besar, cari ke kiri. Karena rentangnya terus menyusut sekitar setengah setiap kali, binary search berjalan dalam waktu $O(\log n)$.

Cara kerja binary search pada daftar terurut

Gunakan daftar terurut ini:

$$[3, 7, 12, 18, 24, 31, 39, 45, 52]$$

Misalkan targetnya adalah $31$.

Mulailah dengan seluruh rentang. Nilai tengahnya adalah $24$. Karena $31 > 24$, semua nilai di sebelah kiri $24$ dapat dibuang, sehingga pencarian berlanjut pada

$$[31, 39, 45, 52]$$

Sekarang nilai tengahnya adalah $39$. Karena $31 < 39$, semua nilai di sebelah kanan $39$ dapat dibuang, sehingga rentangnya menjadi

$$[31]$$

Sekarang nilai tengahnya adalah $31$, jadi pencarian berhenti. Gagasan pentingnya bukan hanya bahwa target ditemukan. Dalam dua perbandingan, rentang kandidat turun dari $9$ nilai menjadi $1$.

Mengapa binary search adalah $O(\log n)$

Setiap perbandingan menghilangkan sekitar setengah dari kandidat yang tersisa. Setelah satu langkah, sekitar $n/2$ item tersisa. Setelah dua langkah, sekitar $n/4$ item tersisa. Setelah $k$ langkah, ukuran yang tersisa kira-kira

$$\frac{n}{2^k}$$

Pencarian selesai ketika jumlah itu kira-kira $1$, sehingga banyaknya langkah memenuhi

$$2^k \approx n$$

Dengan mengambil $\log_2$ pada kedua sisi, diperoleh

$$k \approx \log_2 n$$

Itulah sebabnya binary search dapat diskalakan dengan baik. Pencarian linear mungkin memerlukan hingga $n$ pemeriksaan, tetapi binary search hanya memerlukan cukup banyak pemeriksaan untuk terus membagi dua rentang.

Contoh kode binary search

Berikut adalah versi iteratif standar dalam Python: