1. Linear Search: Menyisir Satu per Satu
Linear search bekerja dengan memeriksa setiap elemen dari indeks pertama hingga terakhir. Cara ini bekerja pada data yang acak, namun jika terdapat 1.000.000 data, pada kasus terburuk kita harus melakukan 1.000.000 pemeriksaan.
2. Binary Search: Kekuatan Membelah Dua
Jika data SUDAH TERURUT (sorted), kita bisa menggunakan Binary Search. Setiap tebakan, kita melihat elemen tengah: jika target lebih kecil, kita buang separuh bagian kanan; jika target lebih besar, kita buang separuh bagian kiri.
Perbandingan Kecepatan Nyata
Untuk mencari 1 nama di antara **1.000.000 data**:
- Linear Search: Butuh hingga **1.000.000 langkah**.
- Binary Search: Maksimal HANYA butuh **20 langkah**! (karena log2(1.000.000) ≈ 20).
Implementasi Binary Search
| 1 | function binarySearch(arrTerurut, target) { |
| 2 | let kiri = 0; |
| 3 | let kanan = arrTerurut.length - 1; |
| 4 | |
| 5 | while (kiri <= kanan) { |
| 6 | const tengah = Math.floor((kiri + kanan) / 2); |
| 7 | |
| 8 | if (arrTerurut[tengah] === target) { |
| 9 | return tengah; // Ditemukan di indeks tengah |
| 10 | } |
| 11 | |
| 12 | if (arrTerurut[tengah] < target) { |
| 13 | kiri = tengah + 1; // Cari di separuh kanan |
| 14 | } else { |
| 15 | kanan = tengah - 1; // Cari di separuh kiri |
| 16 | } |
| 17 | } |
| 18 | |
| 19 | return -1; // Tidak ditemukan |
| 20 | } |
| 21 | |
| 22 | const angka = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]; |
| 23 | console.log(binarySearch(angka, 23)); // Indeks 5 |
Kuis Pemahaman
+10 XP
Apa syarat mutlak agar algoritma Binary Search dapat dijalankan pada sebuah array?