
Contoh Soal Binary Search
Binary search merupakan salah satu algoritma pencarian yang paling efisien dan sering digunakan dalam pemrograman. Dalam artikel ini, kita akan membahas berbagai contoh soal binary search beserta penjelasan detail cara penyelesaiannya. Mari pelajari bersama-sama!
Pengertian Binary Search
Binary search adalah algoritma pencarian yang bekerja dengan cara membagi dua bagian array yang sudah terurut untuk menemukan nilai yang dicari. Metode ini jauh lebih efisien dibandingkan linear search, karena setiap langkah pencarian dapat mengeliminasi setengah dari data yang ada.
Syarat Menggunakan Binary Search
Sebelum menggunakan binary search, ada beberapa syarat yang harus dipenuhi:
- Data harus terurut (ascending atau descending)
- Data harus dapat diakses secara langsung (random access)
- Data harus memiliki struktur yang memungkinkan pembagian dua bagian
Kompleksitas Waktu Binary Search
Binary search memiliki kompleksitas waktu yang sangat efisien:
- Kasus terbaik: O(1)
- Kasus rata-rata: O(log n)
- Kasus terburuk: O(log n)
Contoh Soal Binary Search Tingkat Dasar
Contoh 1: Mencari Angka dalam Array
Berikut adalah contoh soal sederhana untuk memahami konsep dasar binary search:
def binary_search(arr, target): left = 0 right = len(arr) - 1 while left <= right: mid = (left + right) // 2 if arr[mid] == target: return mid elif arr[mid] < target: left = mid + 1 else: right = mid - 1 return -1 # Array terurut numbers = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91] target = 23 result = binary_search(numbers, target) print(f"Angka {target} ditemukan pada indeks ke-{result}")
Contoh 2: Mencari Nama dalam Daftar
def binary_search_string(arr, target): left = 0 right = len(arr) - 1while left <= right: mid = (left + right) // 2 if arr[mid] == target: return mid elif arr[mid] < target: left = mid + 1 else: right = mid - 1 return -1 # Daftar nama terurut names = ["Andi", "Budi", "Citra", "Deni", "Eko", "Fani", "Gita"] target = "Eko" result = binary_search_string(names, target) print(f"Nama {target} ditemukan pada indeks ke-{result}")
Contoh Soal Binary Search Tingkat Menengah
Contoh 3: Mencari Elemen Terdekat
def find_closest(arr, target): if len(arr) == 0: return Noneleft = 0 right = len(arr) - 1while left + 1 < right: mid = (left + right) // 2if arr[mid] == target: return arr[mid] elif arr[mid] < target: left = mid else: right = midif abs(arr[left] - target) <= abs(arr[right] - target): return arr[left] return arr[right]# Array terurut numbers = [1, 3, 6, 7, 9, 11, 14, 17] target = 8 result = find_closest(numbers, target) print(f"Nilai terdekat dengan {target} adalah {result}")
Contoh 4: Mencari Range Nilai
def find_range(arr, target): def find_first(arr, target): left = 0 right = len(arr) - 1 first = -1while left <= right: mid = (left + right) // 2if arr[mid] == target: first = mid right = mid - 1 elif arr[mid] < target: left = mid + 1 else: right = mid - 1return firstdef find_last(arr, target): left = 0 right = len(arr) - 1 last = -1while left <= right: mid = (left + right) // 2if arr[mid] == target: last = mid left = mid + 1 elif arr[mid] < target: left = mid + 1 else: right = mid - 1return lastfirst = find_first(arr, target) last = find_last(arr, target) return [first, last] # Array terurut dengan nilai yang berulang numbers = [1, 2, 2, 2, 3, 4, 4, 5, 5, 5, 6] target = 2 result = find_range(numbers, target) print(f"Range nilai {target} berada pada indeks {result[0]} hingga {result[1]}")
Contoh Soal Binary Search Tingkat Lanjut
Contoh 5: Binary Search pada Array Berputar
def search_rotated(arr, target): left = 0 right = len(arr) - 1while left <= right: mid = (left + right) // 2if arr[mid] == target: return mid# Cek apakah bagian kiri terurut if arr[left] <= arr[mid]: if arr[left] <= target < arr[mid]: right = mid - 1 else: left = mid + 1 # Bagian kanan yang terurut else: if arr[mid] < target <= arr[right]: left = mid + 1 else: right = mid - 1return -1# Array terurut yang diputar numbers = [6, 7, 8, 1, 2, 3, 4, 5] target = 3result = search_rotated(numbers, target) print(f"Nilai {target} ditemukan pada indeks ke-{result}")
Contoh 6: Binary Search untuk Mencari Poin Minimum
def find_minimum(arr): left = 0 right = len(arr) - 1while left < right: mid = (left + right) // 2if arr[mid] > arr[right]: left = mid + 1 else: right = midreturn arr[left]# Array terurut yang diputar numbers = [4, 5, 6, 7, 0, 1, 2]result = find_minimum(numbers) print(f"Nilai minimum dalam array adalah {result}")
Tips Mengerjakan Soal Binary Search
- Pastikan Data Terurut
- Sebelum menggunakan binary search, pastikan data sudah terurut
- Jika belum terurut, urutkan terlebih dahulu menggunakan algoritma sorting
- Identifikasi Kondisi Khusus
- Perhatikan apakah ada kondisi khusus seperti array kosong
- Pertimbangkan kasus array dengan satu elemen
- Cek kemungkinan target tidak ditemukan
- Hindari Integer Overflow
- Saat menghitung nilai tengah, gunakan rumus:
mid = left + (right - left) // 2
- Cara ini lebih aman dibandingkan
(left + right) // 2
- Saat menghitung nilai tengah, gunakan rumus:
- Pastikan Kondisi Terminasi
- Tentukan kondisi berhenti yang tepat (biasanya
left <= right
) - Hindari infinite loop dengan memastikan pointer selalu bergerak
- Tentukan kondisi berhenti yang tepat (biasanya
Latihan Soal Binary Search
Untuk meningkatkan pemahaman, cobalah mengerjakan soal-soal berikut:
- Temukan indeks pertama dari target dalam array terurut yang memiliki duplikat
- Cari elemen terbesar yang lebih kecil dari target
- Implementasikan binary search rekursif
- Temukan titik rotasi dalam array yang diputar
- Cari dua angka dalam array yang jumlahnya sama dengan target
Kesimpulan
Binary search merupakan algoritma pencarian yang sangat efisien dengan kompleksitas O(log n). Dengan memahami berbagai persoalan di atas, Anda dapat menerapkan binary search untuk menyelesaikan berbagai permasalahan pencarian data. Kunci utama dalam menggunakan binary search adalah memastikan data terurut dan mengidentifikasi kondisi khusus yang mungkin terjadi.