Binary Search dan Big O Logaritmik

1. Review Materi Sebelumnya: O(n)

Pada Linear Search, pencarian dilakukan satu per satu dari awal sampai data ditemukan.

Contoh:

Data:
10  20  30  40  50  60  70  80

Cari: 70

Langkah:
10 → bukan
20 → bukan
30 → bukan
40 → bukan
50 → bukan
60 → bukan
70 → ditemukan

Pada kondisi terburuk, semua data harus diperiksa.

Jika jumlah data = n, maka kompleksitasnya:

O(n)

Misalnya:

Jumlah Data	Maksimal Pemeriksaan
10	10
100	100
1.000	1.000
10.000	10.000
1.000.000	1.000.000

Semakin besar data, semakin banyak pemeriksaan.

---

2. Apa Itu O(log n)?

O(log n) adalah kompleksitas algoritma yang pertumbuhannya jauh lebih lambat dibandingkan O(n).

Ide utamanya:

Setiap langkah mengurangi jumlah data yang harus diperiksa menjadi sekitar setengahnya.

Inilah prinsip yang digunakan oleh Binary Search.

---

3. Konsep Dasar Binary Search

Binary Search hanya dapat digunakan jika data sudah terurut.

Contoh:

10  20  30  40  50  60  70  80  90

Misalnya kita mencari:

70

Kita tidak perlu memeriksa dari angka 10 satu per satu.

Kita langsung melihat nilai tengah.

10  20  30  40  [50]  60  70  80  90
                    ↑
                  tengah

Karena:

70 > 50

maka semua data di sebelah kiri 50 bisa dibuang.

Tersisa:

60  70  80  90

Kemudian cari nilai tengah lagi.

60  [70]  80  90
     ↑
   tengah

Ketemu!

---

4. Mengapa O(log n)?

Perhatikan bagaimana jumlah data berkurang.

Misalnya terdapat 16 data:

16
 ↓ dibagi 2
8
 ↓ dibagi 2
4
 ↓ dibagi 2
2
 ↓ dibagi 2
1

Hanya membutuhkan sekitar:

4 langkah

Karena:

16 → 8 → 4 → 2 → 1

Secara matematika:

log₂(16) = 4

Jadi Binary Search mempunyai kompleksitas:

O(log n)

---

5. Contoh dengan 1.024 Data

Misalkan ada:

1.024 data

Binary Search:

1.024
 512
 256
 128
  64
  32
  16
   8
   4
   2
   1

Berapa kali dibagi 2 sampai menjadi 1?

log₂(1024) = 10

Jadi kira-kira hanya membutuhkan 10 kali pemeriksaan.

Bandingkan dengan Linear Search:

Linear Search → maksimal 1.024 pemeriksaan
Binary Search → sekitar 10 pemeriksaan

Ini alasan O(log n) sangat efisien untuk data besar.

---

6. Perbandingan O(n) vs O(log n)

Jumlah Data	O(n)	O(log₂ n)
8	8	3
16	16	4
32	32	5
64	64	6
128	128	7
1.024	1.024	10
10.000	10.000	±14
1.000.000	1.000.000	±20

Terlihat perbedaannya sangat besar.

O(n) bertambah mengikuti jumlah data.

Sedangkan O(log n) bertambah sangat lambat karena setiap langkah mengurangi ruang pencarian menjadi setengah.

---

7. Syarat Binary Search

Ada satu syarat penting:

Data harus sudah terurut.

Contoh yang benar:

10 20 30 40 50 60 70 80 90

Contoh yang tidak bisa langsung digunakan:

50 10 80 30 70 20 90

Harus diurutkan terlebih dahulu.

---

8. Algoritma Binary Search

Misalnya:

Data = [10, 20, 30, 40, 50, 60, 70, 80, 90]

Cari = 70

Algoritmanya:

1. Tentukan posisi awal = 0
2. Tentukan posisi akhir = jumlah data - 1
3. Tentukan posisi tengah
4. Bandingkan data tengah dengan data yang dicari
5. Jika sama → ditemukan
6. Jika nilai yang dicari lebih besar → cari di sebelah kanan
7. Jika nilai yang dicari lebih kecil → cari di sebelah kiri
8. Ulangi sampai ditemukan atau tidak ada data lagi

---

9. Pseudocode Binary Search

ALGORITMA BinarySearch

Input:
    array data
    nilai yang dicari

Deklarasi:
    awal
    akhir
    tengah

awal ← 0
akhir ← jumlah_data - 1

WHILE awal <= akhir DO

    tengah ← (awal + akhir) DIV 2

    IF data[tengah] = nilai THEN
        Tampilkan "Data ditemukan"
        STOP

    ELSE IF nilai > data[tengah] THEN
        awal ← tengah + 1

    ELSE
        akhir ← tengah - 1

    END IF

END WHILE

Tampilkan "Data tidak ditemukan"

---

10. Contoh Manual

Data:

[10, 20, 30, 40, 50, 60, 70, 80, 90]

Cari:

70

Langkah 1

Tengah:

50

Bandingkan:

70 > 50

Maka cari sebelah kanan.

60 70 80 90

Langkah 2

Tengah:

70

Karena:

70 = 70

Maka:

DATA DITEMUKAN

Hanya membutuhkan 2 pemeriksaan, bukan 7 pemeriksaan seperti Linear Search pada contoh tersebut.

---

11. Implementasi Python

def binary_search(data, target):
    awal = 0
    akhir = len(data) - 1

    while awal <= akhir:
        tengah = (awal + akhir) // 2

        if data[tengah] == target:
            return tengah

        elif target > data[tengah]:
            awal = tengah + 1

        else:
            akhir = tengah - 1

    return -1


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

target = 70

hasil = binary_search(data, target)

if hasil != -1:
    print("Data ditemukan pada index", hasil)
else:
    print("Data tidak ditemukan")

Output:

Data ditemukan pada index 6

---

12. Implementasi JavaScript

<!DOCTYPE html>
<html>
<head>
    <title>Binary Search</title>
</head>
<body>

<h2>Binary Search</h2>

<script>

function binarySearch(data, target) {

    let awal = 0;
    let akhir = data.length - 1;

    while (awal <= akhir) {

        let tengah = Math.floor((awal + akhir) / 2);

        if (data[tengah] === target) {
            return tengah;
        }

        else if (target > data[tengah]) {
            awal = tengah + 1;
        }

        else {
            akhir = tengah - 1;
        }
    }

    return -1;
}


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

let target = 70;

let hasil = binarySearch(data, target);

if (hasil !== -1) {
    document.write("Data ditemukan pada index " + hasil);
} else {
    document.write("Data tidak ditemukan");
}

</script>

</body>
</html>

---

13. Perbedaan Linear Search dan Binary Search

Aspek	Linear Search	Binary Search
Kompleksitas	O(n)	O(log n)
Data harus terurut	Tidak	Ya
Cara mencari	Satu per satu	Membagi dua
Data besar	Kurang efisien	Sangat efisien
Prinsip	Sequential	Divide and Conquer

---

14. Analogi Sederhana

Bayangkan mencari nama “Sutrisno” di buku telepon.

Linear Search

Mulai dari halaman pertama:

Halaman 1
Halaman 2
Halaman 3
Halaman 4
...

Satu per satu.

Ini:

O(n)

Binary Search

Buka buku di tengah.

Misalnya nama yang dicari berada setelah halaman tersebut.

Buang setengah buku pertama.

Kemudian buka bagian yang tersisa di tengah lagi.

Buku
 ↓
50%
 ↓
25%
 ↓
12,5%
 ↓
6,25%
 ↓
...

Ini:

O(log n)

---

15. Konsep Penting untuk Dipahami

Yang perlu dipahami bukan hanya hafal:

Binary Search = O(log n)

Tetapi pahami mengapa:

Binary Search mempunyai kompleksitas O(log n) karena pada setiap iterasi ruang pencarian dikurangi menjadi sekitar setengahnya.

Jadi:

n
↓
n/2
↓
n/4
↓
n/8
↓
n/16
↓
...
↓
1

---

16. Latihan

Latihan 1 — Manual

Diberikan data:

[5, 10, 15, 20, 25, 30, 35, 40, 45, 50, 55, 60, 65, 70, 75]

Cari:

65

Tentukan setiap langkah Binary Search:

Langkah 1 → ?
Langkah 2 → ?
Langkah 3 → ?

---

Latihan 2

Data:

[10, 20, 30, 40, 50, 60, 70, 80, 90, 100]

Cari:

20

Buat tabel:

Langkah	Awal	Tengah	Nilai Tengah	Akhir	Keputusan
1	?	?	?	?	?
2	?	?	?	?	?

---

Latihan 3 — Analisis Big O

Bandingkan:

10 data
100 data
1.000 data
10.000 data
100.000 data
1.000.000 data

Hitung perkiraan jumlah pemeriksaan:

Linear Search → O(n)

Binary Search → O(log₂ n)

Tujuan materi ini: mahasiswa mulai melihat bahwa pemilihan algoritma sangat berpengaruh terhadap performa program. Dari O(n) sekarang naik ke O(log n), dan berikutnya bisa dilanjutkan ke O(n log n) melalui algoritma sorting seperti Merge Sort.