Binary search

Masalah

Cari posisi target di array yang sudah terurut, lebih cepat daripada memeriksa satu per satu.

Input / Output

• Input: array terurut a (panjang n), nilai target
• Output: indeks i dengan a[i] == target, atau -1 kalau tidak ada

Ide utama

Bandingkan target dengan elemen tengah. Karena array terurut, separuh bagian yang tidak mungkin berisi target bisa dibuang setiap langkah.

Langkah

1. Set kiri = 0, kanan = n - 1.
2. Selama kiri <= kanan, ambil tengah = kiri + (kanan - kiri) / 2.
3. Kalau a[tengah] == target, kembalikan tengah.
4. Kalau a[tengah] < target, geser kiri = tengah + 1. Kalau tidak, kanan = tengah - 1.
5. Kalau loop selesai tanpa ketemu, kembalikan -1.

Flowchart

flowchart TD
  mulai([Mulai]) --> init[kiri = 0, kanan = n - 1]
  init --> loop{kiri <= kanan?}
  loop -- tidak --> gagal[/return -1/]
  loop -- ya --> mid["tengah = kiri + floor((kanan - kiri) / 2)"]
  mid --> eq{"a[tengah] == target?"}
  eq -- ya --> ok[/return tengah/]
  eq -- tidak --> lt{"a[tengah] < target?"}
  lt -- ya --> kanan_[kiri = tengah + 1]
  lt -- tidak --> kiri_[kanan = tengah - 1]
  kanan_ --> loop
  kiri_ --> loop
  ok --> selesai([Selesai])
  gagal --> selesai

Status rentang pencarian

stateDiagram-v2
  [*] --> Rentang: kiri=0, kanan=n-1
  Rentang --> Ketemu: a[tengah] == target
  Rentang --> Rentang: buang separuh
  Rentang --> Kosong: kiri > kanan
  Ketemu --> [*]
  Kosong --> [*]

Pseudocode

fungsi binarySearch(a, target):
    kiri = 0
    kanan = panjang(a) - 1
    selama kiri <= kanan:
        tengah = kiri + (kanan - kiri) div 2
        jika a[tengah] == target: kembalikan tengah
        jika a[tengah] < target: kiri = tengah + 1
        selain itu: kanan = tengah - 1
    kembalikan -1

Kompleksitas

• Waktu: O(log n), rentang terbelah dua setiap iterasi
• Ruang: O(1)

Edge case

• Array kosong: kanan = -1, loop tidak jalan, hasil -1
• target lebih kecil dari elemen pertama atau lebih besar dari terakhir
• Elemen duplikat: versi ini mengembalikan salah satu indeks, bukan yang paling kiri
• Overflow: pakai kiri + (kanan - kiri) / 2, bukan (kiri + kanan) / 2

Contoh jalan (trace)

a = [2, 5, 8, 12, 16, 23, 38], target = 23

Lihat juga Mulai di sini.