Pencarian · Pelajaran 2 dari 10
Pencarian biner
10 menit baca · BelajarCode
Jika data sudah urut, ada cara yang jauh lebih cepat: pencarian biner. Idenya sama dengan mencari kata di kamus: buka bagian tengah, lalu tentukan apakah yang dicari ada di separuh kiri atau kanan.
Algoritmanya
- Tandai batas kiri
kiri = 0dan batas kanankanan = n - 1. - Selama
kiri <= kanan, ambil posisi tengahtengah = (kiri + kanan) // 2. - Jika data di tengah sama dengan target, selesai.
- Jika data di tengah lebih kecil dari target, target pasti ada di kanan:
kiri = tengah + 1. - Jika lebih besar, target pasti ada di kiri:
kanan = tengah - 1. - Jika
kiri > kanan, target tidak ada.
Jejak mencari 23
Data: [3, 8, 12, 15, 23, 31, 42, 56, 67, 75] (indeks 0 sampai 9).
| Langkah | kiri | kanan | tengah | data[tengah] | Keputusan |
|---|---|---|---|---|---|
| 1 | 0 | 9 | 4 | 23 | Sama dengan target, selesai |
Kebetulan langsung ketemu. Sekarang cari 67:
| Langkah | kiri | kanan | tengah | data[tengah] | Keputusan |
|---|---|---|---|---|---|
| 1 | 0 | 9 | 4 | 23 | 23 < 67, geser kiri ke 5 |
| 2 | 5 | 9 | 7 | 56 | 56 < 67, geser kiri ke 8 |
| 3 | 8 | 9 | 8 | 67 | Sama, selesai di indeks 8 |
Hanya 3 perbandingan, sedangkan pencarian linear butuh 9.
1def cari_biner(data, target):2 kiri, kanan = 0, len(data) - 13 langkah = 04 while kiri <= kanan:5 langkah += 16 tengah = (kiri + kanan) // 27 if data[tengah] == target:8 return tengah, langkah9 elif data[tengah] < target:10 kiri = tengah + 111 else:12 kanan = tengah - 113 return -1, langkah1415data = [3, 8, 12, 15, 23, 31, 42, 56, 67, 75]16print(cari_biner(data, 67))17print(cari_biner(data, 20))1819besar = list(range(1, 1_000_001))20print(cari_biner(besar, 765432))(8, 3) (-1, 4) (765431, 20)
Untuk sejuta data, pencarian biner hanya butuh sekitar 20 langkah, karena 2 pangkat 20 sudah lebih dari satu juta.
Versi rekursif
1def cari_biner_rekursif(data, target, kiri, kanan):2 if kiri > kanan:3 return -14 tengah = (kiri + kanan) // 25 if data[tengah] == target:6 return tengah7 if data[tengah] < target:8 return cari_biner_rekursif(data, target, tengah + 1, kanan)9 return cari_biner_rekursif(data, target, kiri, tengah - 1)1011data = [3, 8, 12, 15, 23, 31, 42, 56, 67, 75]12print(cari_biner_rekursif(data, 42, 0, len(data) - 1))6
Kesalahan yang sering terjadi
- Memakai data yang belum urut. Hasilnya bisa salah tanpa pesan error apa pun. - Menulis while kiri < kanan sehingga kasus satu data terakhir terlewat. - Menulis kiri = tengah alih-alih tengah + 1, sehingga perulangan bisa macet selamanya.
Pustaka bawaan
Python punya modul bisect yang menjalankan pencarian biner pada list urut, misalnya bisect.bisect_left(data, x) untuk mencari posisi pertama yang nilainya tidak kurang dari x.
Cek pemahaman
Pencarian biner pada 1.024 data urut membutuhkan paling banyak berapa langkah?
Latihan
Menghitung kemunculan
Pada data urut [1, 2, 2, 2, 3, 5, 5, 8], hitung berapa kali angka 2 muncul tanpa memeriksa semua data. Petunjuk: cari posisi pertama yang nilainya tidak kurang dari 2, dan posisi pertama yang nilainya lebih dari 2, keduanya dengan pencarian biner.
Pembahasan
1def batas_bawah(data, x):2 kiri, kanan = 0, len(data)3 while kiri < kanan:4 tengah = (kiri + kanan) // 25 if data[tengah] < x:6 kiri = tengah + 17 else:8 kanan = tengah9 return kiri1011def batas_atas(data, x):12 kiri, kanan = 0, len(data)13 while kiri < kanan:14 tengah = (kiri + kanan) // 215 if data[tengah] <= x:16 kiri = tengah + 117 else:18 kanan = tengah19 return kiri2021data = [1, 2, 2, 2, 3, 5, 5, 8]22print(batas_atas(data, 2) - batas_bawah(data, 2))23print(batas_atas(data, 5) - batas_bawah(data, 5))24print(batas_atas(data, 4) - batas_bawah(data, 4))3 2 0
Versi ini memakai batas kanan len(data) dan syarat kiri < kanan, karena yang dicari adalah posisi sisipan, bukan data tertentu. Hasilnya sama dengan bisect_right(data, x) - bisect_left(data, x).
Jalankan contoh kode di pelajaran ini tanpa instalasi lewat compiler Python online.