Penjelasan binary search: cara kerja, kode, dan kompleksitas

Masalah apa yang diselesaikan binary search

Linear search memeriksa item satu per satu dan butuh hingga n perbandingan. Jika datanya terurut, Anda bisa jauh lebih baik: bandingkan target dengan item tengah, dan Anda langsung tahu separuh mana yang dipertahankan. Idenya sama seperti mencari kata di kamus cetak.

Binary search juga berfungsi pada apa pun yang monoton, bukan hanya array. Jika sebuah kondisi ya/tidak bernilai false untuk semua nilai kecil dan true untuk semua nilai besar, binary search menemukan batasnya. Ini disebut binary search pada jawaban.

Contoh langkah demi langkah

Cari 23 dalam list terurut [2, 5, 8, 12, 16, 23, 38, 56, 72, 91] (indeks 0 sampai 9). Simpan dua indeks, lo dan hi, yang membatasi rentang yang masih perlu diperiksa.

Tiga perbandingan, bukan enam seperti pemindaian linear. Untuk list berisi sejuta item, binary search paling banyak butuh 20.

Implementasi Python

Versi iteratif di bawah memakai rentang tertutup [lo, hi]: kedua ujungnya masih kandidat. Perulangan berjalan selama rentang tidak kosong.

def binary_search(items, target):
    lo, hi = 0, len(items) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if items[mid] == target:
            return mid
        if items[mid] < target:
            lo = mid + 1          # target is in the right half
        else:
            hi = mid - 1          # target is in the left half
    return -1                     # not found
data = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
print(binary_search(data, 23))   # 5
print(binary_search(data, 7))    # -1

Dalam kode Python sehari-hari, pakai modul pustaka standar bisect. bisect_left mengembalikan posisi paling kiri tempat target bisa disisipkan sambil menjaga list tetap terurut, yang sekaligus menunjukkan apakah target ada.

from bisect import bisect_left, bisect_right, insort
data = [1, 3, 3, 3, 7, 9]
i = bisect_left(data, 3)
print(i, bisect_right(data, 3))   # 1 4  (3 occupies indexes 1..3)
print(i < len(data) and data[i] == 3)   # True: 3 is present
print(bisect_left(data, 5))       # 4: insertion point for 5
insort(data, 5)
print(data)                       # [1, 3, 3, 3, 5, 7, 9]

Kompleksitas waktu dan ruang

Varian: pertama, terakhir, dan binary search pada jawaban

Banyak soal tidak menanyakan apakah suatu nilai ada, melainkan di mana batasnya: indeks pertama dengan nilai minimal x, kemunculan terakhir x, atau bilangan terkecil yang memenuhi suatu kondisi. Pakai rentang setengah terbuka [lo, hi) dan jangan pernah berhenti lebih awal.

def first_true(lo, hi, ok):
    """Smallest x in [lo, hi) with ok(x) True, or hi if none.
    ok must be False...False True...True over the range."""
    while lo < hi:
        mid = (lo + hi) // 2
        if ok(mid):
            hi = mid          # mid may be the answer, keep it
        else:
            lo = mid + 1      # mid is too small
    return lo
data = [1, 3, 3, 3, 7, 9]
print(first_true(0, len(data), lambda i: data[i] >= 3))   # 1
# Integer square root of 200: largest x with x*x <= 200
print(first_true(0, 201, lambda x: x * x > 200) - 1)      # 14

• Lower bound (indeks pertama dengan nilai ≥ x): bisect_left.
• Upper bound (indeks pertama dengan nilai > x): bisect_right.
• Jumlah x dalam list terurut: bisect_right(a, x) - bisect_left(a, x).
• Pencarian pada rotated sorted array, mencari puncak (peak finding), dan meminimalkan nilai maksimum (misalnya kapasitas terkecil yang bisa mengirim semua paket dalam D hari) adalah varian klasik di wawancara kerja.

Kesalahan umum

• Mencampur konvensi rentang. Dengan rentang tertutup pakai lo <= hi dan hi = mid - 1; dengan rentang setengah terbuka pakai lo < hi dan hi = mid. Mencampurnya menyebabkan perulangan tak terbatas atau elemen yang terlewat.
• Menulis lo = mid alih-alih lo = mid + 1. Ketika hi = lo + 1, mid sama dengan lo dan perulangan tidak pernah berakhir.
• Menjalankan binary search pada data tak terurut. Hasilnya salah tanpa error apa pun.
• Integer overflow pada (lo + hi) / 2 di bahasa dengan integer berukuran tetap seperti Java, C, dan C++. Pakai lo + (hi - lo) / 2. Integer Python tidak overflow, jadi (lo + hi) // 2 aman.
• Mengembalikan kecocokan pertama yang ditemukan padahal soal meminta kemunculan pertama di antara duplikat.

Kapan memakai binary search

Pemakaian di dunia nyata mencakup indeks database dan file system (B-tree menggeneralisasi idenya), git bisect untuk mencari commit yang memunculkan bug, mencari nilai dalam tabel rentang terurut seperti blok IP, dan banyak masalah numerik yang mencari sebuah ambang (threshold).