Carian binari mencari sasaran dalam array tersusun dengan berulang kali membahagikan julat carian separuh. Setiap perbandingan menghapuskan separuh daripada elemen yang tinggal, memberikan masa O(log n).
Tilik elemen tengah. Jika ia sama dengan sasaran, selesai. Jika sasaran lebih kecil, cari separuh kiri; jika lebih besar, cari separuh kanan. Ulangi sehingga ditemui atau julat 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 mesti tersusun — sebaliknya hasilnya tidak bermakna. Hati-hati dengan pepijat off-by-one dalam lo/hi dan limpahan integer dalam beberapa bahasa (gunakan lo + (hi-lo)//2).
Mengurangkan separuh ruang carian mengubah pencarian satu juta elemen menjadi kira-kira 20 perbandingan.
Corak membahagi-dan-takluk di sebaliknya muncul semula dalam pokok, pangkalan data, dan banyak masalah temu duga.
Mengetahui satu keperluan ketatnya — input tersusun — menjaga anda daripada pepijat halus klasik.