Binary search mencari nilai di array yang sudah terurut dengan cara membelah dua: cek angka di tengah, lalu buang separuh yang pasti gak berisi target. Tiap langkah, sisa datanya tinggal setengah. Mirip main tebak angka 1 sampai 100: kamu tebak 50, dijawab "lebih besar", jadi angka 1 sampai 50 gak perlu dipikir lagi.
🧪 Tebakan cepat: di tebak angka 1 sampai 100, kalau kamu selalu menebak angka tengah, paling banyak butuh berapa tebakan: 7, 50, atau 100? Tebak dulu, jawabannya ada di bagian "Kenapa cepat sekali".
Cara kerjanya
Cari 13 di [1, 3, 5, 7, 9, 11, 13, 15, 17, 19] (10 angka, index 0 sampai 9). left dan right adalah batas kiri dan kanan bagian yang masih mungkin berisi target, dan mid adalah index di tengahnya.
| Langkah | left |
right |
mid |
arr[mid] |
Keputusan |
|---|---|---|---|---|---|
| 1 | 0 | 9 | 4 | 9 | 9 < 13, buang kiri: left = 5 |
| 2 | 5 | 9 | 7 | 15 | 15 > 13, buang kanan: right = 6 |
| 3 | 5 | 6 | 5 | 11 | 11 < 13, buang kiri: left = 6 |
| 4 | 6 | 6 | 6 | 13 | sama, ketemu di index 6 |
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; // buang separuh kiri
else right = mid - 1; // buang separuh kanan
}
return -1; // gak ada
}
const arr = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19];
console.log(binarySearch(arr, 13)); // 6
console.log(binarySearch(arr, 4)); // -1
left = 0danright = arr.length - 1: awalnya semua index masih mungkin.while (left <= right)mengulang selama masih ada yang bisa dicek. Pakai<=, bukan<: kalau tinggal satu angka (leftsama denganright), angka itu tetap harus dicek. Dengan<, angka paling kiri atau paling kanan bisa terlewat.Math.floor(...)membulatkan ke bawah.(5 + 6) / 2hasilnya5.5, padahal index harus bilangan bulat, jadimidjadi 5.arr[mid]lebih kecil dari target? Target pasti di kanan:left = mid + 1. Lebih besar? Target di kiri:right = mid - 1. Ada+ 1dan- 1karenamidsudah dicek.- Kalau
leftsudah melewatiright, gak ada sisa yang bisa dicek, jadi hasilnya-1.
Satu langkah adalah satu kali mengecek arr[mid]. Di tabel tadi ada 4 langkah.
Syarat: datanya harus terurut
Binary search cuma benar di data yang sudah terurut. Dari angka di tengah, dia menyimpulkan "target pasti di kanan" karena semua angka di kirinya lebih kecil. Di data acak, kesimpulan itu salah, dan gak ada error yang muncul: hasilnya salah diam-diam. binarySearch([5, 1, 9, 3, 7], 1) mengembalikan -1, padahal 1 ada di index 1.
Kenapa cepat sekali
Tiap langkah membuang setengah sisa data. 100 angka jadi 50, 25, 12, 6, 3, lalu 1: paling banyak 7 langkah. Itu jawaban tebakannya.
| Banyak data | Linear search, paling banyak | Binary search, paling banyak |
|---|---|---|
| 100 | 100 langkah | 7 langkah |
| 1.000 | 1.000 langkah | 10 langkah |
| 1.000.000 | 1.000.000 langkah | 20 langkah |
Banyaknya data disebut n. Binary search ditulis O(log n): datanya dua kali lipat, langkahnya cuma nambah satu. log n artinya berapa kali n bisa dibelah dua sampai tinggal 1. Bandingkan dengan linear search yang O(n): datanya dua kali lipat, langkahnya ikut dua kali lipat.
⚠️ Jebakan yang sering ketemu
left = midtanpa+ 1. Waktuleftdanrightbersebelahan,midsama denganleftterus, dan loop-nya gak pernah berhenti.- Lupa
Math.floor.arr[3.5]ituundefined, jadi perbandingannya salah dan targetnya gak ketemu. - Mencetak angkanya langsung.
console.log(3)memang mencetak 3, tapi yang diuji adalah hasilbinarySearch(...). Cetak hasil pemanggilan function-nya.
TL;DR: Binary search mencari di array terurut. Cek mid = Math.floor((left + right) / 2): sama berarti ketemu, lebih kecil berarti left = mid + 1, lebih besar berarti right = mid - 1. Ulangi selama left <= right, lalu kembalikan -1 kalau habis. Tiap langkah membuang separuh data, jadi O(log n): 1.000 data sekitar 10 langkah, 1 juta data sekitar 20. Datanya harus terurut, kalau gak hasilnya salah tanpa error.
