Pencarian Biner (Binary Search)

Gambaran Besar Dulu

Bayangin kamu lagi main tebak angka sama teman. Kamu mikirkan angka 1 sampai 100, temanmu harus nebak. Ada dua tipe teman:

Teman A (polos): nebak dari 1, 2, 3, 4… satu per satu. Bisa kena di percobaan ke-99. Capek banget.

Teman B (cerdas): nebak 50 dulu. Kamu bilang “lebih besar.” Dia nebak 75. “Lebih kecil.” Dia nebak 62… dan seterusnya. Paling lama 7 kali tebak, pasti ketemu.

Teman B itu pakai strategi binary search. Teman A pakai linear search. Nah, itu inti dari materi hari ini.

Syarat Mutlak: Data Harus Sudah Urut

Ini bagian yang sering dilupakan, jadi wajib diingat.

Binary search hanya bisa dipakai kalau datanya sudah terurut, entah dari kecil ke besar atau sebaliknya. Kalau belum urut, binary search tidak akan jalan dengan benar.

Logikanya simpel: strategi “cari di setengah kanan” hanya masuk akal kalau kamu tahu bahwa semua angka di kanan memang lebih besar. Kalau datanya acak, kamu tidak bisa tahu itu.

Cara Kerja Binary Search: Step by Step

Ambil daftar ini sebagai contoh kerja:

[1, 3, 4, 5, 6, 7, 8, 9, 11, 12, 14, 15, 19, 20, 22]
 0  1  2  3  4  5  6  7   8   9  10  11  12  13  14   ← indeks

Target yang dicari: 19

Langkah 1: Temukan elemen tengah

Total ada 15 elemen (indeks 0 sampai 14). Tengahnya ada di indeks 7. Isinya angka 9.

Bandingkan: 19 vs 9. 19 lebih besar dari 9.

Artinya: 19 pasti ada di sebelah kanan. Setengah kiri (indeks 0-7) langsung dibuang semua.

Langkah 2: Cari di sisa sebelah kanan

Sisa data yang dilirik: [11, 12, 14, 15, 19, 20, 22] (indeks 8-14).

Tengahnya sekarang di indeks 11. Isinya angka 15.

Bandingkan: 19 vs 15. 19 lebih besar.

Buang lagi setengah kiri. Sisa yang diperiksa tinggal indeks 12-14.

Langkah 3: Cari di sisa yang tersisa

Sisa: [19, 20, 22] (indeks 12-14).

Tengahnya di indeks 13. Isinya angka 20.

Bandingkan: 19 vs 20. 19 lebih kecil.

Buang setengah kanan. Sisa tinggal indeks 12 saja.

Langkah 4: Cek terakhir

Indeks 12 isinya 19. Cocok! Ditemukan.

Total perbandingan: 4 kali.

Bandingkan dengan Linear Search

Kalau pakai cara biasa (lihat satu per satu dari depan), untuk menemukan angka 19 di daftar yang sama kamu harus melewati posisi 1, 3, 4, 5, 6, 7, 8, 9, 11, 12, 14, 15… baru ketemu 19 di perbandingan ke-13.

Selisihnya besar. Dan itu baru untuk 15 data.

Semakin Besar Data, Semakin Terasa Bedanya

Di sinilah binary search benar-benar menunjukkan kelebihannya.

Setiap langkah binary search membuang separuh data. Jadi untuk n elemen, paling banyak butuh log₂(n) perbandingan.

• 15 elemen → maksimal 4 perbandingan
• 1.000 elemen → maksimal 10 perbandingan
• 1.000.000 elemen → maksimal 20 perbandingan

Linear search untuk 1 juta elemen? Bisa sampai 1 juta perbandingan di kasus terburuk. Binary search? Cukup 20.

Jebakan yang Sering Terjadi

Ada beberapa kesalahan yang umum dilakukan pemula:

Data belum diurutkan tapi langsung pakai binary search. Hasilnya salah dan tidak bisa diprediksi. Kalau data belum urut, urutkan dulu. Pengurutan memang butuh waktu tambahan, tapi itu biaya yang perlu dibayar.

Salah menghitung indeks tengah. Kalau rentangnya dari indeks 8 ke 14, tengahnya bukan 7. Rumusnya: (awal + akhir) / 2. Jadi (8 + 14) / 2 = 11. Bukan angka yang ditebak asal.

Bingung kapan berhenti. Binary search berhenti di dua kondisi: ketemu, atau rentang pencarian habis (kiri > kanan). Kalau rentang habis dan belum ketemu, berarti data tidak ada di daftar.

Aktivitas: Main Tebak Angka

Ini cara paling mudah untuk merasakan langsung cara kerjanya.

Satu siswa pikirkan angka antara 1 sampai 100 (diam, tidak boleh bilang). Siswa lain menebak dengan aturan: selalu tebak angka tengah dari rentang yang masih mungkin.

Contoh jalannya:

• Tebak 50. Jawaban: “lebih besar.” Rentang jadi 51-100.
• Tebak 75. Jawaban: “lebih kecil.” Rentang jadi 51-74.
• Tebak 62. Dan seterusnya.

Dengan strategi ini, angka mana pun antara 1-100 pasti ketemu dalam maksimal 7 tebakan. Coba buktikan.

Kuis Singkat

1. Kamu punya daftar angka [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]. Kamu mencari angka 23. Pada langkah pertama binary search, elemen mana yang dibandingkan duluan, dan apa keputusannya setelah perbandingan itu?

2. Temanmu bilang: “Aku mau pakai binary search untuk mencari nama di daftar absensi yang belum diurutkan.” Apa yang harus kamu sampaikan ke temanmu, dan kenapa?

3. Untuk sebuah daftar yang berisi 1.024 elemen, berapa maksimal perbandingan yang dibutuhkan binary search? (Petunjuk: 2¹⁰ = 1.024)