Contoh Soal dan Solusi Binary Search: Panduan Lengkap
Pencarian biner adalah algoritma pencarian yang efisien untuk menemukan item tertentu dalam array yang sudah terurut. Algoritma ini bekerja dengan membagi array menjadi dua bagian secara berulang hingga item yang dicari ditemukan atau array menjadi kosong. Kecepatan dan efisiensinya menjadikannya pilihan populer dalam berbagai aplikasi pemrograman. Artikel ini akan memberikan contoh soal dan solusi lengkap untuk membantu Anda memahami cara kerja pencarian biner.
Memahami Konsep Dasar Binary Search
Sebelum kita masuk ke contoh soal, mari kita ulas kembali konsep dasar pencarian biner:
- Array Terurut: Pencarian biner hanya bekerja pada array yang sudah terurut (ascending atau descending).
- Pembagian Dua Bagian: Algoritma ini membagi array menjadi dua bagian di setiap iterasi.
- Perbandingan Tengah: Nilai tengah array dibandingkan dengan nilai yang dicari.
- Iterasi Berulang: Proses pembagian dan perbandingan diulang hingga nilai ditemukan atau array habis.
Contoh Soal 1: Mencari Angka dalam Array
Soal: Temukan angka 17 dalam array terurut berikut: [2, 5, 7, 11, 17, 23, 29, 31].
Solusi:
-
Langkah Awal: Nilai tengah array adalah 11. Karena 17 > 11, pencarian berlanjut pada bagian kanan array: [17, 23, 29, 31].
-
Iterasi Kedua: Nilai tengah bagian kanan adalah 23. Karena 17 < 23, pencarian berlanjut pada bagian kiri: [17].
-
Nilai Ditemukan: Nilai 17 ditemukan.
Implementasi dalam Python:
def binary_search(arr, target):
low = 0
high = len(arr) - 1
while low <= high:
mid = (low + high) // 2
if arr[mid] == target:
return mid # Nilai ditemukan
elif arr[mid] < target:
low = mid + 1 # Cari di bagian kanan
else:
high = mid - 1 # Cari di bagian kiri
return -1 # Nilai tidak ditemukan
arr = [2, 5, 7, 11, 17, 23, 29, 31]
target = 17
result = binary_search(arr, target)
if result != -1:
print("Nilai ditemukan pada indeks:", result)
else:
print("Nilai tidak ditemukan")
Contoh Soal 2: Mencari Kata dalam Daftar Terurut
Soal: Temukan kata "apel" dalam daftar terurut berikut: ["anggur", "apel", "jeruk", "mangga", "pisang"].
Solusi: Prinsipnya sama seperti contoh sebelumnya, hanya saja kita membandingkan string. Pencarian biner akan secara efisien menemukan indeks "apel".
Contoh Soal 3: Menangani Array Kosong atau Nilai Tidak Ditemukan
Soal: Cari angka 10 dalam array kosong [] dan dalam array [2, 5, 7, 11, 17].
Solusi: Algoritma pencarian biner harus mampu menangani kasus array kosong dan situasi di mana nilai yang dicari tidak ada dalam array. Implementasi Python di atas sudah mencakup penanganan kasus ini dengan mengembalikan nilai -1.
Kesimpulan
Pencarian biner merupakan algoritma yang sangat efisien untuk menemukan item dalam array terurut. Memahami konsep dasar dan contoh-contoh di atas akan membantu Anda dalam mengimplementasikannya dengan efektif dalam program Anda. Ingatlah bahwa efisiensi pencarian biner sangat bergantung pada array yang sudah terurut. Jika array tidak terurut, maka Anda perlu mengurutkannya terlebih dahulu sebelum menggunakan pencarian biner. Ini akan mempengaruhi kompleksitas waktu keseluruhan.
