Binary Search — Algoritma Pencarian O(log n) dengan Diagram Animasi
Binary search adalah algoritma pencarian O(log n) yang setiap langkah potong array setengah. Pahami cara kerja, implementasi Go, trace langkah demi langkah, dan variasi lower/upper bound.
Bayangin lo punya buku telepon setebal 1000 halaman dan lo nyari nama "Hermes". Lo buka halaman 1, baca satu-satu sampai ketemu? Butuh 1000 langkah. Atau lo buka tengah, liat apakah "Hermes" ada di kiri atau kanan, terus ulang? Cuma 10 langkah.
Itu binary search. Algoritma paling dasar yang setiap developer harus paham — dan salah satu contoh paling jelas kenapa O(log n) jauh lebih efisien dari O(n).
Binary Search — Cara Kerjanya dalam Diagram
Binary search bekerja dengan prinsip divide and conquer. Setiap langkah, array dipotong setengah — bagian yang gak mungkin berisi target dibuang. Diagram di bawah punya edge dengan animasi dot yang bergerak dari satu node ke node lain, nunjukin alur data secara visual.
Diagram di atas punya animated edges — dot biru bergerak dari satu node ke node lain, nunjukin alur data. Node Start, Found, dan Not Found berpulse glow. Ini bikin alur eksekusi lebih gampang diikuti secara visual.
Kode Binary Search di Go
Implementasi binary search di Go cukup straightforward. Kuncinya: array harus sudah terurut.
Perhatikan `mid := left + (right-left)/2` — ini mencegah integer overflow. Kalau lo pake `(left+right)/2`, bisa overflow kalau left+right > 2³¹-1.
Trace — Liat Langkah demi Langkah
Misal array `[2, 5, 8, 12, 16, 23, 38, 45, 56, 72]` dan target `23`. Ini tracenya:
Cuma 3 langkah dari 10 item. Bayangin kalau array-nya 1 juta item — binary search butuh maksimal 20 langkah (log₂ 1.000.000 ≈ 20). Linear search butuh 1 juta langkah.
Binary Search vs Linear Search — Visual Comparison
Diagram berikut nunjukin perbandingan jumlah langkah antara binary search (O(log n)) dan linear search (O(n)). Dot bergerak dari kiri ke kanan nunjukin alur perbandingan:
Lihat perbedaan di n=1 juta: binary search 20 langkah vs linear search 1 juta langkah. Itu beda antara 20 detik dan 11 hari (kalau 1 langkah = 1 ms).
Variasi Binary Search
Binary search gak cuma buat nyari nilai exact. Ada beberapa variasi yang sering dipake:
Lower bound — nyari index pertama di mana arr[i] >= target. Berguna buat binary search di array yang punya duplikat.
Upper bound — nyari index pertama di mana arr[i] > target. Pasangan lower bound + upper bound bisa ngitung berapa banyak kemunculan target.
Binary search juga bisa dipake di domain non-array. Contoh: nyari akar kuadrat, nyari threshold optimal di parameter tuning, atau nyari batas kecepatan di sistem scheduling.
Penutup — Binary Search Itu Dimana-mana
Binary search adalah algoritma yang lo pake setiap hari tanpa sadar. Git bisect? Binary search. Database index lookup? Binary search. Debugging production issue dengan nge-split log setengah-setengah? Binary search.
Paham binary search berarti lo paham konsep divide and conquer, logarithmic scaling, dan invariant loop — tiga konsep yang fundamental di computer science. Dan yang paling penting: lo jadi bisa milih algoritma yang tepat pas data lo mulai gede.
