Dalam algoritma dan pemrograman, kita tidak hanya perlu mengetahui apakah sebuah program dapat menghasilkan output yang benar. Kita juga perlu memahami seberapa efisien algoritma tersebut ketika jumlah data semakin besar.
Salah satu konsep penting dalam analisis algoritma adalah Big O Notation.
Salah satu jenis Big O yang sangat penting untuk dipahami adalah O(log n) atau kompleksitas logaritmik.
Contoh algoritma yang menggunakan konsep O(log n) adalah Binary Search.
Artikel ini akan membahas pengertian O(log n), cara kerja Binary Search, contoh program JavaScript, serta perhitungan matematikanya secara step by step.
Apa Itu Big O?
Big O adalah notasi yang digunakan untuk menggambarkan pertumbuhan kebutuhan waktu atau jumlah operasi sebuah algoritma berdasarkan jumlah data yang diproses.
Beberapa kompleksitas yang umum digunakan antara lain:
| Big O | Nama | Contoh |
|---|---|---|
| O(1) | Constant | Mengambil data berdasarkan index |
| O(log n) | Logarithmic | Binary Search |
| O(n) | Linear | Sequential Search |
| O(n log n) | Linearithmic | Merge Sort |
| O(n²) | Quadratic | Nested Loop |
| O(2ⁿ) | Exponential | Rekursif tertentu |
| O(n!) | Factorial | Permutasi |
Semakin lambat pertumbuhan jumlah operasi terhadap n, secara umum semakin baik skalabilitas algoritmanya.
Apa Itu O(log n)?
O(log n) disebut kompleksitas logaritmik.
Ciri utamanya adalah setiap proses mengurangi ukuran masalah secara signifikan, biasanya menjadi setengah dari ukuran sebelumnya.
Misalnya terdapat 16 data.
Pada Binary Search:
16 → 8 → 4 → 2 → 1
Setiap langkah membagi ruang pencarian menjadi dua.
Secara matematis:
log₂(16) = 4
Artinya dibutuhkan sekitar 4 kali pembagian untuk mengurangi 16 data menjadi 1 bagian.
Apa Itu Binary Search?
Binary Search adalah algoritma pencarian yang bekerja dengan cara membagi data menjadi dua bagian secara berulang.
Namun ada satu syarat penting:
Data harus sudah dalam keadaan terurut.
Contoh:
1001, 1002, 1003, 1004, 1005,
1006, 1007, 1008, 1009, 1010
Misalnya kita ingin mencari NIM:
1008
Binary Search tidak memeriksa data mulai dari 1001 satu per satu.
Program langsung memeriksa data yang berada di tengah.
Contoh Data
Kita memiliki 10 data:
Index : 0 1 2 3 4 5 6 7 8 9
Data : 1001 1002 1003 1004 1005 1006 1007 1008 1009 1010
Target yang ingin dicari:
1008
Langkah 1: Menentukan Batas Pencarian
Awalnya:
kiri = 0
kanan = 9
Karena index terakhir adalah 9.
Kemudian mencari posisi tengah:
tengah = (kiri + kanan) / 2
Masukkan nilai:
tengah = (0 + 9) / 2
= 9 / 2
= 4,5
Karena index harus berupa bilangan bulat, digunakan pembulatan ke bawah:
tengah = 4
Dalam JavaScript:
Math.floor((kiri + kanan) / 2)
Maka:
data[4] = 1005
Sekarang bandingkan:
1005 dengan 1008
Karena:
1005 < 1008
maka target berada di sebelah kanan.
Bagian berikutnya tidak perlu diperiksa:
1001 1002 1003 1004 1005
Pencarian dilanjutkan dari:
kiri = tengah + 1
kiri = 4 + 1
kiri = 5
Sehingga area pencarian menjadi:
1006 1007 1008 1009 1010
Langkah 2: Mencari Nilai Tengah Lagi
Sekarang:
kiri = 5
kanan = 9
Hitung:
tengah = (5 + 9) / 2
= 14 / 2
= 7
Maka:
data[7] = 1008
Bandingkan:
1008 = 1008
Data ditemukan.
Jadi hanya diperlukan:
2 langkah
Perjalanan Pencarian Secara Visual
Prosesnya dapat digambarkan:
DATA AWAL
1001 1002 1003 1004 1005 1006 1007 1008 1009 1010
↑
tengah
1005
1008 > 1005
→ cari ke kanan
DATA BERIKUTNYA
1006 1007 1008 1009 1010
↑
tengah
1008
1008 = 1008
→ DITEMUKAN
Mengapa Kompleksitasnya O(log n)?
Sekarang kita masuk ke bagian matematikanya.
Prinsip Binary Search adalah:
Setiap langkah → data dibagi 2
Misalnya:
n = 16
16
↓ dibagi 2
8
↓ dibagi 2
4
↓ dibagi 2
2
↓ dibagi 2
1
Jumlah pembagian:
4 kali
Secara matematika:
16 / 2⁴ = 1
atau:
2⁴ = 16
Maka:
4 = log₂(16)
Jadi:
log₂(16) = 4
Inilah dasar mengapa Binary Search mempunyai kompleksitas:
O(log n)
Contoh dengan 32 Data
Jika jumlah data:
n = 32
Maka:
32 → 16 → 8 → 4 → 2 → 1
Ada 5 kali pembagian.
Secara matematika:
log₂(32) = 5
Jadi:
O(log₂ 32) = O(5)
Dalam notasi Big O, basis logaritma biasanya tidak dituliskan karena perbedaan konstanta basis tidak mengubah kelas kompleksitas.
Sehingga ditulis:
O(log n)
Contoh dengan 1.024 Data
Sekarang bayangkan sistem mempunyai 1.024 data.
Jika menggunakan Binary Search:
1.024
↓
512
↓
256
↓
128
↓
64
↓
32
↓
16
↓
8
↓
4
↓
2
↓
1
Berapa kali pembagian?
10 kali
Karena:
2¹⁰ = 1.024
Maka:
log₂(1.024) = 10
Jadi meskipun terdapat 1.024 data, ruang pencarian dapat dipersempit hanya dalam sekitar 10 tahap pembagian.
Contoh dengan 1.048.576 Data
Sekarang jumlah data menjadi:
1.048.576
Kita cari:
log₂(1.048.576)
Karena:
2²⁰ = 1.048.576
maka:
log₂(1.048.576) = 20
Artinya Binary Search hanya membutuhkan sekitar 20 kali pembagian untuk mencapai satu kandidat data.
Perhatikan perbandingan berikut:
| Jumlah Data | log₂(n) |
|---|---|
| 16 | 4 |
| 32 | 5 |
| 64 | 6 |
| 128 | 7 |
| 256 | 8 |
| 512 | 9 |
| 1.024 | 10 |
| 2.048 | 11 |
| 4.096 | 12 |
| 65.536 | 16 |
| 1.048.576 | 20 |
Inilah karakteristik O(log n): jumlah data dapat bertambah sangat besar, tetapi jumlah langkah pencarian bertambah relatif lambat.
Program Binary Search dengan JavaScript
Berikut contoh implementasinya:
<!DOCTYPE html>
<html>
<head>
<title>Binary Search</title>
</head>
<body>
<h2>Pencarian Data Mahasiswa</h2>
<p>Data NIM:</p>
<p>
1001, 1002, 1003, 1004, 1005,
1006, 1007, 1008, 1009, 1010
</p>
<input type="number" id="cari" placeholder="Masukkan NIM">
<button onclick="cariData()">Cari</button>
<p id="hasil"></p>
<script>
let data = [
1001, 1002, 1003, 1004, 1005,
1006, 1007, 1008, 1009, 1010
];
function cariData() {
let target =
Number(document.getElementById("cari").value);
let kiri = 0;
let kanan = data.length - 1;
let langkah = 0;
let ditemukan = false;
while (kiri <= kanan) {
langkah++;
let tengah =
Math.floor((kiri + kanan) / 2);
if (data[tengah] === target) {
ditemukan = true;
document.getElementById("hasil").innerHTML =
"Data ditemukan: " + data[tengah] +
"<br>Index: " + tengah +
"<br>Jumlah langkah: " + langkah;
break;
} else if (data[tengah] < target) {
kiri = tengah + 1;
} else {
kanan = tengah - 1;
}
}
if (ditemukan == false) {
document.getElementById("hasil").innerHTML =
"Data tidak ditemukan" +
"<br>Jumlah langkah: " + langkah;
}
}
</script>
</body>
</html>
Hubungan Setiap Bagian Program dengan Algoritma
Bagian:
let kiri = 0;
let kanan = data.length - 1;
digunakan untuk menentukan batas area pencarian.
Bagian:
let tengah = Math.floor((kiri + kanan) / 2);
digunakan untuk menentukan posisi tengah.
Bagian:
if (data[tengah] === target)
digunakan untuk memeriksa apakah data ditemukan.
Bagian:
else if (data[tengah] < target) {
kiri = tengah + 1;
}
berarti target berada di sebelah kanan.
Sedangkan:
else {
kanan = tengah - 1;
}
berarti target berada di sebelah kiri.
Dengan demikian, setiap perulangan mengurangi area pencarian.
Perbandingan Sequential Search dan Binary Search
Misalnya terdapat 1.000 data.
Sequential Search
Pencarian dilakukan satu per satu:
1001
1002
1003
1004
...
Kompleksitas:
O(n)
Binary Search
Pencarian dilakukan dengan membagi area menjadi dua:
1000
↓
500
↓
250
↓
125
↓
...
Kompleksitas:
O(log n)
Namun Binary Search memiliki syarat bahwa data harus sudah terurut.
Kesimpulan
O(log n) adalah kompleksitas logaritmik yang memiliki karakteristik bahwa ukuran masalah berkurang secara signifikan pada setiap langkah.
Binary Search merupakan contoh klasik algoritma O(log n).
Prinsip dasarnya sangat sederhana:
Cari data
↓
Ambil nilai tengah
↓
Bandingkan
↓
Buang setengah data
↓
Cari lagi
↓
Ulangi
Secara matematis:
n / 2ᵏ = 1
Maka:
n = 2ᵏ
Sehingga:
k = log₂(n)
Itulah alasan kompleksitas Binary Search adalah:
O(log n)
Konsep ini penting dalam Algoritma dan Pemrograman karena membantu kita memahami bahwa ketika jumlah data semakin besar, pemilihan algoritma dapat memberikan perbedaan yang sangat besar terhadap jumlah proses yang harus dilakukan komputer.
Kasus Data Tidak Ditemukan
Selain kondisi ketika data berhasil ditemukan, Binary Search juga harus menangani kondisi ketika data yang dicari tidak terdapat di dalam array.
Misalnya kita memiliki data:
1001, 1002, 1003, 1004, 1005,
1006, 1007, 1008, 1009, 1010
Kemudian kita mencari:
1015
Data 1015 tidak terdapat dalam array.
Langkah 1
Kondisi awal:
kiri = 0
kanan = 9
Hitung nilai tengah:
tengah = floor((0 + 9) / 2)
= floor(4,5)
= 4
Data pada index 4:
data[4] = 1005
Bandingkan:
1005 < 1015
Karena target lebih besar, pencarian dilanjutkan ke kanan.
kiri = tengah + 1
kiri = 5
Sekarang area pencarian:
1006 1007 1008 1009 1010
Langkah 2
Sekarang:
kiri = 5
kanan = 9
Hitung:
tengah = floor((5 + 9) / 2)
= 7
Data:
data[7] = 1008
Bandingkan:
1008 < 1015
Maka pencarian kembali bergerak ke kanan:
kiri = tengah + 1
kiri = 8
Langkah 3
Sekarang:
kiri = 8
kanan = 9
Hitung:
tengah = floor((8 + 9) / 2)
= floor(8,5)
= 8
Data:
data[8] = 1009
Bandingkan:
1009 < 1015
Maka:
kiri = tengah + 1
kiri = 9
Langkah 4
Sekarang:
kiri = 9
kanan = 9
Hitung:
tengah = floor((9 + 9) / 2)
= 9
Data:
data[9] = 1010
Bandingkan:
1010 < 1015
Maka:
kiri = tengah + 1
kiri = 10
Sekarang kondisi:
kiri = 10
kanan = 9
Perhatikan:
kiri > kanan
Maka kondisi while:
while (kiri <= kanan)
menjadi:
10 <= 9
Hasilnya:
false
Perulangan berhenti.
Karena data tidak ditemukan, program menjalankan:
if (ditemukan == false) {
document.getElementById("hasil").innerHTML =
"Data tidak ditemukan" +
"<br>Jumlah langkah: " + langkah;
}
Output:
Data tidak ditemukan
Jumlah langkah: 4
Mengapa kiri > kanan Berarti Data Tidak Ditemukan?
Ini merupakan konsep penting dalam Binary Search.
Selama:
kiri <= kanan
masih terdapat area yang mungkin berisi data yang dicari.
Tetapi ketika:
kiri > kanan
area pencarian sudah kosong.
Contohnya:
kiri = 10
kanan = 9
Tidak mungkin lagi terdapat index yang berada di antara 10 dan 9.
Dengan demikian, kita dapat menyimpulkan bahwa data tidak ditemukan.
Visualisasi
Data:
1001 1002 1003 1004 1005 1006 1007 1008 1009 1010
|----|----|----|----|----|----|----|----|----|----|
0 1 2 3 4 5 6 7 8 9
Target = 1015
Pencarian terus bergerak ke kanan:
1001 1002 1003 1004 1005 | 1006 1007 1008 1009 1010
↓
kanan
Kemudian:
1006 1007 1008 1009 1010
↓
1009
Kemudian:
1010
↓
1010 < 1015
Akhirnya:
kiri = 10
kanan = 9
kiri > kanan
↓
Data tidak ditemukan
Perbedaan Dua Kondisi Akhir
Binary Search memiliki dua kemungkinan hasil:
1. Data ditemukan
Ketika:
data[tengah] === target
Program langsung berhenti.
Contoh:
Target = 1008
data[7] = 1008
1008 === 1008
→ Data ditemukan
2. Data tidak ditemukan
Ketika:
kiri > kanan
Program berhenti karena sudah tidak ada area yang dapat dicari.
Contoh:
Target = 1015
kiri = 10
kanan = 9
10 > 9
→ Data tidak ditemukan
Kompleksitas Saat Data Tidak Ditemukan
Menariknya, kasus data tidak ditemukan tetap memiliki kompleksitas:
O(log n)
Mengapa?
Karena meskipun data tidak ada, Binary Search tetap membagi area pencarian menjadi dua pada setiap langkah.
Misalnya terdapat 1.024 data:
1024
↓
512
↓
256
↓
128
↓
64
↓
32
↓
16
↓
8
↓
4
↓
2
↓
1
↓
0
Jumlah langkah tetap berada pada orde logaritmik.
Secara matematis:
log₂(1024) = 10
Jadi pencarian data yang tidak ditemukan juga dapat diselesaikan dalam sekitar 10 tahap pembagian, bukan harus memeriksa seluruh 1.024 data satu per satu.
Kesimpulan Kasus Data Tidak Ditemukan
Dalam Binary Search, kondisi berhenti dapat terjadi karena dua hal:
Binary Search
│
┌────────┴────────┐
│ │
Data ditemukan Data tidak ditemukan
│ │
data[mid] === target kiri > kanan
│ │
STOP STOP
Jadi, kondisi:
while (kiri <= kanan)
sangat penting karena menjadi batas selama masih ada area pencarian.
Ketika:
kiri > kanan
artinya seluruh kemungkinan posisi data sudah diperiksa dan data tersebut tidak terdapat dalam array.
Baik ketika data ditemukan maupun tidak ditemukan, Binary Search memiliki kompleksitas waktu O(log n) pada kasus pencarian berbasis pembagian dua seperti ini.
