Pengertian Binary Search
Binary search (pencarian biner) adalah algoritma pencarian yang bekerja dengan prinsip divide and conquer: membagi ruang pencarian menjadi dua bagian secara berulang sehingga jumlah elemen yang perlu diperiksa semakin kecil di setiap iterasi.
Tujuannya menemukan elemen tertentu dalam sebuah dataset. Keunggulan utamanya adalah efisiensi: hanya memerlukan O(log n) iterasi, jauh lebih cepat daripada linear search yang butuh O(n).
Nama "binary" merujuk pada cara kerjanya yang selalu membagi dua. Ini adalah wujud klasik strategi divide and conquer: pecahkan masalah besar menjadi dua sub-masalah yang lebih kecil, selesaikan dengan membuang separuh yang tidak relevan, dan ulangi. Setiap iterasi memangkas ruang pencarian hingga setengahnya — pertumbuhan yang sangat lambat inilah esensi O(log n).
Syarat Utama: Data Harus Terurut
Satu batasan utama binary search: data harus dalam kondisi terurut sebelum pencarian dilakukan, misalnya terurut menaik. Tanpa keterurutan, algoritma tidak bisa memutuskan separuh mana yang menyimpan target.
Jika data belum terurut, langkah pengurutan wajib dilakukan dulu — dan biaya pengurutan ini perlu diperhitungkan karena bisa menambah kompleksitas keseluruhan bila pencarian hanya dilakukan sesekali.
Prinsip Perbandingan Elemen Tengah
Inti cara kerja binary search adalah membandingkan elemen target dengan elemen tengah (mid) dari dataset:
- Jika elemen target sama dengan elemen tengah → pencarian berhenti, data ditemukan.
- Jika target lebih kecil dari elemen tengah → pencarian dilanjutkan ke bagian kiri.
- Jika target lebih besar → pencarian dilanjutkan ke bagian kanan.
Proses ini diulangi hingga elemen target ditemukan atau seluruh ruang pencarian habis diperiksa.
Langkah-Langkah Algoritma
Langkah-langkah binary search secara umum:
- Tentukan pointer awal (low) dan akhir (high) dari array.
- Hitung elemen tengah: mid = (low + high) / 2.
- Jika elemen tengah adalah yang dicari → kembalikan indeksnya.
- Jika target lebih kecil → cari di separuh pertama (high = mid - 1).
- Jika target lebih besar → cari di separuh kedua (low = mid + 1).
- Ulangi selama low <= high; jika loop berakhir tanpa temuan → data tidak ada.
Perhatikan rumus indeks tengah: mid = (low + high) / 2 dengan pembagian bulat (floor). Pada implementasi nyata, batas low dan high adalah indeks array, bukan nilai data. Variabel steps kadang ditambahkan untuk mencatat jumlah iterasi hingga data ditemukan — metrik yang dipakai dalam studi kinerja algoritma.
Contoh Perhitungan Manual
Misalkan array terurut: {2, 5, 8, 12, 16, 23, 38, 56, 72, 91}, target = 72.
- Langkah 1: low=0, high=9, mid=(0+9)/2=4 → arr[4]=16. Target 72 > 16, ruang pencarian bergerak ke kanan (low=5).
- Langkah 2: low=5, high=9, mid=7 → arr[7]=56. Target 72 > 56, lanjut kanan (low=8).
- Langkah 3: low=8, high=9, mid=8 → arr[8]=72. Cocok — data ditemukan di indeks 8.
Hanya 3 perbandingan untuk 10 data — bandingkan dengan linear search yang butuh hingga 9 perbandingan.
Kompleksitas Waktu O(log n)
Setiap iterasi mengeliminasi separuh ruang pencarian, sehingga jumlah langkah tumbuh secara logaritmik. Untuk 1 juta data terurut, binary search butuh maksimal sekitar 20 perbandingan.
Linear search dengan kompleksitas O(n) bisa butuh 1 juta perbandingan untuk data yang sama. Selisih ini yang membuat binary search wajib dikuasai developer.
Untuk konteks: 1 miliar data hanya butuh ~30 perbandingan dengan binary search, versus hingga 1 miliar perbandingan dengan linear search. Inilah alasan algoritma ini menjadi fondasi indeks basis data dan sistem pencarian modern — ia membuat pencarian pada data raksasa terasa instan.
Implementasi Iteratif vs Rekursif
Ada dua cara implementasi:
- Iteratif: memakai loop while low <= high; hemat memori karena tidak memakai call stack.
- Rekursif: fungsi memanggil dirinya sendiri dengan batas baru (low, mid-1 atau mid+1, high); lebih ringkas dibaca tetapi memakai memori stack.
Keduanya punya kompleksitas waktu O(log n). Untuk menghindari overflow pada array besar, hitung tengah dengan mid = low + (high - low) / 2.
Perbandingan memori: versi iteratif hanya memakai beberapa variabel (low, high, mid) — O(1) memori tambahan. Versi rekursif memakai O(log n) frame stack. Untuk array raksasa atau environment memori ketat (embedded), iteratif lebih aman; untuk keterbacaan kode, rekursif sering dipilih.
Kapan Binary Search Gagal?
Pencarian dinyatakan gagal ketika low > high tanpa menemukan target — ruang pencarian tidak bisa dibagi lagi. Implementasi umumnya mengembalikan -1 sebagai tanda data tidak ditemukan.
Kesalahan umum pemula: lupa memastikan data terurut, salah update batas (misalnya high = mid bukan mid-1) sehingga infinite loop, atau memakai perbandingan yang salah arah.
Penerapan di Dunia Nyata
Binary search dipakai di banyak sistem nyata:
- Basis data: mengelola indeks untuk akses data cepat.
- Sistem file terstruktur: menemukan file dalam sistem yang diindeks.
- Katalog produk: mencari barang dalam daftar produk e-commerce.
- Perpustakaan digital: pencarian ISBN dalam koleksi terurut.
- Sistem stok gudang: mencari ID barang dalam daftar terurut.
Contoh yang diteliti secara akademik: pencarian ISBN pada sistem perpustakaan digital dan pencarian ID barang pada sistem stok gudang — keduanya memakai binary search pada daftar terurut untuk menemukan data dalam hitungan milidetik, lengkap dengan pencatatan jumlah iterasi (steps) sebagai metrik efisiensi.
Binary Search vs Linear Search
- Binary search: O(log n), sangat cepat untuk data besar, wajib data terurut.
- Linear search: O(n), sederhana, tidak butuh data terurut, unggul untuk data kecil atau pencarian sekali jalan.
Aturan praktis: data besar dan sering dicari → urutkan sekali, pakai binary search. Data kecil atau jarang dicari → linear search cukup.
Aturan praktis memilih algoritma: data besar + sering dicari → urutkan sekali, pakai binary search berkali-kali; data kecil atau pencarian sesekali → linear search lebih sederhana; data dinamis dengan banyak sisip/hapus → struktur data seperti binary search tree lebih tepat daripada array terurut.
Analisis Efisiensi: Angka Nyata
Keunggulan binary search terlihat jelas pada data besar. Dengan kompleksitas O(log n), mencari dalam 1 juta data butuh maksimal sekitar 20 perbandingan — karena 2^20 ≈ 1.048.576.
Bandingkan dengan linear search O(n) yang bisa butuh hingga 1 juta perbandingan untuk data yang sama. Untuk 1 miliar data, binary search butuh ~30 langkah; linear search bisa butuh 1 miliar. Selisih inilah alasan binary search menjadi materi wajib struktur data.
Perbandingan konkret: pada array 10 elemen contoh di atas, binary search butuh 3 langkah versus maksimal 9 langkah linear search. Pada 1.000.000 elemen, binary search butuh ~20 langkah versus hingga 1.000.000 langkah. Keunggulannya membesar eksponensial seiring data.
Contoh Implementasi Python
Implementasi iteratif dalam Python:
- def binary_search(arr, target): low, high = 0, len(arr)-1
- while low <= high: mid = low + (high - low) // 2
- Jika arr[mid] == target → return mid
- Jika arr[mid] < target → low = mid + 1
- Jika arr[mid] > target → high = mid - 1
- Jika loop selesai → return -1
Versi rekursif memakai logika sama tetapi memanggil fungsi itu sendiri pada separuh yang relevan. Keduanya O(log n); versi iteratif lebih hemat memori.
Tips implementasi: selalu uji dengan array kecil (0, 1, 2 elemen) dan kasus tepi — target di awal, di akhir, tidak ada, dan array kosong. Bug off-by-one hampir selalu lolos pada array besar tetapi tertangkap pada kasus kecil.
Kesalahan Umum & Kapan Tidak Memakainya
Jebakan yang sering dialami pemula:
- Lupa mengurutkan data — binary search pada data acak memberi hasil salah tanpa error yang jelas.
- Integer overflow: mid = (low + high) // 2 bisa overflow pada array sangat besar; gunakan low + (high - low) // 2.
- Off-by-one: salah update batas (misalnya high = mid bukan mid-1) menyebabkan infinite loop atau elemen terlewat.
- Kondisi loop salah: gunakan low <= high agar elemen terakhir tetap diperiksa.
Binary search juga bukan solusi universal: untuk data kecil linear search lebih sederhana; untuk data dinamis yang sering disisipi/dihapus, menjaga keterurutan itu mahal — pertimbangkan binary search tree atau hash table; dan untuk pencarian sekali jalan pada data acak, biaya pengurutan O(n log n) mengalahkan manfaatnya.
Pertanyaan Umum
Apa itu binary search?
Binary search (pencarian biner) adalah algoritma pencarian yang menemukan elemen dalam data terurut dengan cara membagi ruang pencarian menjadi dua bagian secara berulang. Setiap iterasi mengeliminasi separuh kemungkinan lokasi, sehingga sangat cepat untuk data besar.
Apa syarat utama binary search?
Data harus sudah terurut (misalnya menaik) sebelum pencarian dilakukan. Tanpa data terurut, pembagian separuh tidak bisa menentukan sisi mana yang menyimpan target, sehingga algoritma tidak valid.
Bagaimana langkah kerja binary search?
Tentukan batas bawah (low) dan batas atas (high); hitung indeks tengah mid = (low+high)/2; bandingkan elemen tengah dengan target; jika sama selesai; jika target lebih kecil lanjut ke separuh kiri (high = mid-1); jika lebih besar lanjut ke separuh kanan (low = mid+1); ulangi sampai ketemu atau ruang habis.
Apa itu kompleksitas O(log n)?
O(log n) artinya jumlah langkah tumbuh sangat lambat dibanding ukuran data. Untuk 1 juta data, binary search butuh maksimal sekitar 20 perbandingan, sedangkan pencarian linear bisa butuh 1 juta perbandingan.
Apa beda binary search dan linear search?
Linear search memeriksa elemen satu per satu dari awal (O(n)) dan tidak butuh data terurut. Binary search membagi data dua bagian tiap langkah (O(log n)) tetapi wajib data terurut.
Bisakah binary search dipakai pada data tidak terurut?
Tidak secara langsung. Data harus diurutkan dulu, dan biaya pengurutan (misalnya O(n log n)) bisa menghapus keuntungan binary search jika pencarian hanya dilakukan sekali.
Apa contoh penggunaan binary search di dunia nyata?
Pencarian pada basis data dan indeksnya, pencarian file dalam sistem terindeks, pencarian barang di katalog produk e-commerce, pencarian ISBN di perpustakaan digital, dan pengecekan nilai dalam daftar terurut.
Bagaimana cara menghitung indeks tengah yang aman?
Gunakan mid = low + (high - low) / 2 (pembagian bulat) agar terhindar dari overflow bilangan bulat yang bisa terjadi pada (low + high) / 2 untuk array sangat besar.