Binary Search membagi data menjadi dua setiap langkah. Syarat: data harus terurut.

Kompleksitas: O(log n) — untuk 1 juta data, hanya perlu ~20 langkah!

Cara kerja:

1. Lihat elemen tengah
2. Jika target = tengah → ketemu!
3. Jika target < tengah → cari di separuh kiri
4. Jika target > tengah → cari di separuh kanan
5. Ulangi sampai ketemu atau habis

function binarySearch(arr, target) {
  let left = 0;
  let right = arr.length - 1;

  while (left <= right) {
    const mid = Math.floor((left + right) / 2);

    if (arr[mid] === target) return mid;
    if (arr[mid] < target) left = mid + 1;
    else right = mid - 1;
  }

  return -1;
}

const sorted = [1, 3, 5, 7, 9, 11, 13, 15];
binarySearch(sorted, 7);  // 3
binarySearch(sorted, 10); // -1

Perbandingan dengan Linear Search:

Variasi: Cari posisi insert

function searchInsert(arr, target) {
  let left = 0, right = arr.length - 1;
  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    if (arr[mid] === target) return mid;
    if (arr[mid] < target) left = mid + 1;
    else right = mid - 1;
  }
  return left; // Posisi di mana target seharusnya
}

🎭 Analogi sehari-hari: Tebak angka 1-1000. Kamu nebak "500?". Jawaban "lebih besar". Tebak "750?". "Lebih kecil". Tebak "625?"... Setiap tebakan buang setengah kemungkinan. Maximum 10 tebakan untuk 1000 angka (2¹⁰=1024). Itulah binary search — sistematis buang setengah.

💡 (left + right) / 2 bug terkenal: Untuk left dan right yang besar, left + right bisa overflow integer (di Java, C++). Solusi: left + (right - left) / 2. Di JavaScript aman karena number = float64, tapi tetap praktik bagus.

⚠️ Jebakan umum:

• Off-by-one di left/right bound — pakai left <= right atau left < right beda hasil. Pikir teliti edge case "1 elemen tersisa"
• Lupa data harus sorted — binary search di unsorted = hasil random. Tidak ada warning
• Infinite loop kalau left = mid tanpa +1 saat target > mid. Selalu mid + 1 atau mid - 1
• Equality di mid sebelum kiri/kanan — kalau salah urut, miss target

🎯 Variant binary search interview:

• Cari occurrence pertama dari nilai duplikat → binary, kalau ketemu cek kiri terus
• Cari rotated sorted array → binary modifikasi
• Cari di matrix sorted → binary di flatten virtual
• Square root → binary dari 0 sampai n
• First bad version (LeetCode 278) → binary

🧪 Tebakan cepat: 1jt elemen sorted. Berapa langkah max? log₂(1jt) ≈ 20. Itu kenapa Google bisa search trilyunan halaman dalam millidetik (variant indexed).

TL;DR: Binary Search = bagi dua tiap langkah, syarat sorted. O(log n). Mantra: setiap iterasi setengah possibility hilang. Hati-hati off-by-one dan integer overflow.