Binary Search adalah algoritma untuk mencari sebuah data dengan cara membagi area pencarian menjadi dua bagian setiap kali melakukan pencarian.

Syarat pentingnya:

Data harus sudah terurut.

Contoh data:

let data = [10, 20, 30, 40, 50, 60, 70, 80, 90, 100];

Kita ingin mencari:

let target = 70;

---

1. Kalau menggunakan pencarian biasa

Misalnya kita mencari angka 70 dari awal:

10 → 20 → 30 → 40 → 50 → 60 → 70

Kita harus mengecek:

1. 10
2. 20
3. 30
4. 40
5. 50
6. 60
7. 70

Jadi perlu 7 pengecekan.

Ini termasuk:$$O(n)$$

---

2. Binary Search

Binary Search tidak mulai dari angka pertama.

Dia langsung mengambil nilai tengah.

Data:

10  20  30  40  50  60  70  80  90  100
                ↑
              tengah

Nilai tengahnya adalah:

50

Kita ingin mencari:

70

Bandingkan:

70 > 50

Berarti 70 tidak mungkin berada di sebelah kiri 50.

Maka bagian kiri kita buang.

10 20 30 40 50 | 60 70 80 90 100
                XXXXXXXXX

Sekarang kita hanya mencari di:

60 70 80 90 100

---

3. Cari tengah lagi

Dari:

60 70 80 90 100

Nilai tengahnya:

80

Bandingkan:

70 < 80

Berarti kita buang bagian kanan.

60 70 | 80 90 100
        XXXXXXXXX

Sekarang tersisa:

60 70

---

4. Cari lagi

Dari:

60 70

Kita menemukan:

70

🎯 Data ditemukan!

---

5. Visualisasinya

Prosesnya seperti ini:

DATA AWAL
10 20 30 40 50 60 70 80 90 100
            ↓
          TENGAH
            50
            ↓
      70 > 50
            ↓
BUANG SEBELAH KIRI
            ↓

60 70 80 90 100
        ↓
      TENGAH
        80
        ↓
    70 < 80
        ↓
BUANG SEBELAH KANAN
        ↓

60 70
   ↓
  70
   ↓
KETEMU 🎯

---

6. Program JavaScript

Sekarang kita lihat programnya.

let data = [10, 20, 30, 40, 50, 60, 70, 80, 90, 100];

let target = 70;

let kiri = 0;
let kanan = data.length - 1;

while (kiri <= kanan) {

    let tengah = Math.floor((kiri + kanan) / 2);

    console.log("Mengecek:", data[tengah]);

    if (data[tengah] === target) {
        console.log("Data ditemukan!");
        console.log("Index:", tengah);
        break;
    }

    if (data[tengah] < target) {
        kiri = tengah + 1;
    } else {
        kanan = tengah - 1;
    }
}

---

7. Apa fungsi kiri dan kanan?

Bagian ini penting:

let kiri = 0;
let kanan = data.length - 1;

kiri menunjukkan posisi awal pencarian.

kiri = 0

Sedangkan:

kanan = 9

karena array mempunyai 10 data:

index:
 0   1   2   3   4   5   6   7   8   9
10  20  30  40  50  60  70  80  90 100

---

8. Bagaimana mendapatkan tengah?

Ini:

let tengah = Math.floor((kiri + kanan) / 2);

Awalnya:

kiri = 0
kanan = 9

Maka:$$(0+9)/2 = 4,5$$

Karena index harus bilangan bulat:

Math.floor(4.5)

hasilnya:

4

Jadi:

tengah = 4

Index 4 adalah:

50

---

9. Bagian paling penting

Perhatikan:

if (data[tengah] < target) {
    kiri = tengah + 1;
}

Artinya:

Kalau nilai tengah lebih kecil daripada target, cari ke kanan.

Contoh:

50 < 70

Maka:

kiri = tengah + 1

Kita pindah ke:

60 70 80 90 100

Sebaliknya:

else {
    kanan = tengah - 1;
}

Artinya:

Kalau nilai tengah lebih besar daripada target, cari ke kiri.

Contoh:

80 > 70

Maka:

kanan = tengah - 1

---

10. Kenapa Binary Search = O(log n)?

Ini hubungannya dengan pertanyaan kita sebelumnya.

Misalkan ada:

n = 100

Binary Search tidak mencari 100 data satu per satu.

Dia membagi:

100
 ↓
50
 ↓
25
 ↓
12
 ↓
6
 ↓
3
 ↓
1

Jadi sekitar 7 langkah.

Secara matematis:$$\log_2(100) \approx 6,64$$

atau kira-kira:$$\boxed{7\ langkah}$$

---

🧠 Kesimpulan sederhana

Binary Search:

Data harus terurut
        ↓
Ambil data tengah
        ↓
Bandingkan dengan target
        ↓
Target lebih besar?
→ Cari ke kanan
        ↓
Target lebih kecil?
→ Cari ke kiri
        ↓
Ulangi
        ↓
Ketemu

Dan karena setiap pencarian membuang kira-kira setengah data, kompleksitasnya adalah: O(logn)​