Binary search menemukan target dalam array terurut dengan berulang kali membagi dua rentang pencarian. Setiap perbandingan menghilangkan setengah dari elemen yang tersisa, memberikan waktu O(log n).
Lihat elemen tengah. Jika sama dengan target, selesai. Jika target lebih kecil, cari setengah kiri; jika lebih besar, cari setengah kanan. Ulangi sampai ditemukan atau rentang kosong.
def binary_search(arr, target):
lo, hi = 0, len(arr) - 1
while lo <= hi:
mid = (lo + hi) // 2 # middle index
if arr[mid] == target:
return mid # found it
elif arr[mid] < target:
lo = mid + 1 # discard left half
else:
hi = mid - 1 # discard right half
return -1 # not present
binary_search([1, 3, 5, 7, 9], 7) # -> 3
Search 7 in [1,3,5,7,9]
lo=0 hi=4 mid=2 -> 5 < 7 => lo=3
lo=3 hi=4 mid=3 -> 7 == 7 => return 3
Input harus terurut — jika tidak, hasilnya tidak bermakna. Hati-hati dengan bug off-by-one di lo/hi dan integer overflow di beberapa bahasa (gunakan lo + (hi-lo)//2).
Membagi dua ruang pencarian mengubah pencarian elemen satu juta menjadi ~20 perbandingan.
Pola divide-and-conquer di baliknya muncul kembali dalam pohon, database, dan banyak masalah interview.
Mengetahui satu persyaratan ketatnya — input terurut — menjauhkan Anda dari bug klasik yang halus.