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:

  1. Data harus terurut (ascending atau descending)
  2. Data harus dapat diakses secara langsung (random access)
  3. 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

  1. Pastikan Data Terurut
    • Sebelum menggunakan binary search, pastikan data sudah terurut
    • Jika belum terurut, urutkan terlebih dahulu menggunakan algoritma sorting
  2. Identifikasi Kondisi Khusus
    • Perhatikan apakah ada kondisi khusus seperti array kosong
    • Pertimbangkan kasus array dengan satu elemen
    • Cek kemungkinan target tidak ditemukan
  3. Hindari Integer Overflow
    • Saat menghitung nilai tengah, gunakan rumus: mid = left + (right - left) // 2
    • Cara ini lebih aman dibandingkan (left + right) // 2
  4. Pastikan Kondisi Terminasi
    • Tentukan kondisi berhenti yang tepat (biasanya left <= right)
    • Hindari infinite loop dengan memastikan pointer selalu bergerak

Latihan Soal Binary Search

Untuk meningkatkan pemahaman, cobalah mengerjakan soal-soal berikut:

  1. Temukan indeks pertama dari target dalam array terurut yang memiliki duplikat
  2. Cari elemen terbesar yang lebih kecil dari target
  3. Implementasikan binary search rekursif
  4. Temukan titik rotasi dalam array yang diputar
  5. 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.

Back to top button
Close

Adblock Terdeteksi

LidahTekno.com didukung oleh iklan Google Adsense untuk menyediakan konten bagi Anda. Mohon pertimbangkan untuk menonaktifkan AdBlocker atau menambahkan kami ke dalam whitelist Anda agar kami dapat terus memberikan informasi dan tips teknologi terbaik. Terima kasih atas dukungan Anda!