Searching — sequential & binary search

Dua cara mencari elemen di array, kenapa binary search jauh lebih cepat, dan jebakan klasik saat menulisnya.

Searching adalah mencari posisi sebuah nilai (biasa disebut key) di dalam kumpulan data. Ada dua algoritma dasar yang wajib dikuasai: sequential search dan binary search.

Sequential search

Cara paling jujur: cek elemen satu per satu dari depan sampai ketemu atau habis.

function SeqSearch(input A: array[0..n-1] of integer, input x: integer) → integer
{ mengembalikan indeks x di A, atau -1 jika tidak ada }
Deklarasi
  i : integer
Algoritma
  i ← 0
  while (i < n) and (A[i] ≠ x) do
    i ← i + 1
  endwhile
  if i < n then → i else → -1

Tidak butuh data terurut.
Kasus terbaik 1 perbandingan, terburuk $n$ perbandingan, jadi kompleksitasnya $O(n)$ .

Binary search

Kalau data sudah terurut, kita bisa jauh lebih pintar: lihat elemen tengah, lalu buang setengah bagian yang pasti tidak berisi x. Persis seperti mencari kata di kamus.

Setiap langkah membuang separuh data: $n \to n/2 \to n/4 \to \dots \to 1$ . Banyaknya langkah adalah berapa kali $n$ bisa dibagi 2, yaitu $\lceil \log_2 (n+1) \rceil$ . Untuk satu juta data, cukup 20 perbandingan.

n	sequential (terburuk)	binary (terburuk)
1.000	1.000	10
1.000.000	1.000.000	20
1.000.000.000	1.000.000.000	30

Versi rekursif

Binary search juga bisa ditulis rekursif, karena masalahnya mengecil menjadi “cari di setengah bagian”:

function bs(a: number[], x: number, lo = 0, hi = a.length - 1): number {
  if (lo > hi) return -1;                   // base case: rentang kosong
  const mid = (lo + hi) >> 1;
  if (a[mid] === x) return mid;
  return a[mid] < x ? bs(a, x, mid + 1, hi) : bs(a, x, lo, mid - 1);
}

Praktikkan di soal Binary Search dan Cari Posisi Sisip.

Telusuri interval pencarian

Cari 12 pada array terurut [2, 4, 7, 9, 12, 15]. Indeks dimulai dari nol dan batas kanan ikut diperiksa.

Binary search pada enam indeks

	0	1	2	3	4	5
Nilai	2	4	7	9	12	15
Status	lo	·	mid	·	·	hi

1/3Periksa tengah. Indeks tengah 2 bernilai 7. Target lebih besar, jadi buang indeks 0 sampai 2.lo = 0 · hi = 5 · mid = 2