Pencarian Biner Klasik: Kiri, Kanan, Tengah
Implementasikan pencarian biner secara iteratif dan rekursif, kuasai detail batas lo/hi agar tidak salah satu posisi, lalu verifikasi kebenarannya dengan input kasus tepi.
Pencarian Biner Klasik: Kiri, Kanan, Tengah adalah pelajaran Coding Interview Prep gratis di CoddyKit. Ini adalah pelajaran 1 dari 4. Kamu bisa membaca pelajaran lengkapnya di bawah secara gratis — lalu praktikkan langsung di browser dengan editor kode bawaan dan tutor AI 24/7. Ini adalah bagian dari jalur belajar Coding Interview Prep, dan progresmu tersinkronisasi di web dan aplikasi CoddyKit. Kursus Coding Interview Prep mencakup 4 pelajaran total.
Mengapa Pencarian Biner Penting
Pencarian biner mengurangi pemindaian linear O(n) menjadi O(log n) dengan membagi dua ruang pencarian pada setiap langkah. Dalam larik berisi satu juta elemen, pemindaian linear memerlukan hingga 1.000.000 perbandingan, sedangkan pencarian biner memerlukan paling banyak 20. Efisiensi ini menjadikannya salah satu algoritme yang paling sering diujikan dalam wawancara pemrograman.
Wawasan utamanya adalah bahwa larik terurut memungkinkan Anda memutuskan, setelah satu perbandingan, bagian mana dari separuh data yang tersisa dapat langsung dibuang seluruhnya.
Kerangka Kiri, Tengah, Kanan
Pencarian biner menggunakan tiga penunjuk indeks: lo (batas kiri), hi (batas kanan), dan mid (titik tengah). Pada setiap iterasi, Anda menghitung mid = (lo + hi) // 2 dan membandingkan sasaran dengan arr[mid]. Jika sasaran lebih kecil, ubah hi = mid - 1; jika lebih besar, ubah lo = mid + 1; jika sama, sasaran ditemukan.
Perulangan berlanjut selama lo <= hi. Jika perulangan berakhir tanpa menemukan sasaran, kembalikan -1.
def binary_search(arr, target):
lo, hi = 0, len(arr) - 1
while lo <= hi:
mid = (lo + hi) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
lo = mid + 1
else:
hi = mid - 1
return -1
print(binary_search([1, 3, 5, 7, 9, 11], 7)) # 3
print(binary_search([1, 3, 5, 7, 9, 11], 6)) # -1Menghindari Luapan Bilangan Bulat pada Titik Tengah
Ekspresi mid = (lo + hi) // 2 dapat menyebabkan luapan bilangan bulat dalam bahasa dengan bilangan bulat berlebar tetap (Java, C++). Bilangan bulat Python memiliki presisi sembarang, sehingga luapan tidak pernah terjadi, tetapi pewawancara tetap mengharapkan Anda mengetahui alternatif yang aman: mid = lo + (hi - lo) // 2.
Bentuk ini menghitung titik tengah yang sama, tetapi hanya menambahkan setengah jarak ke lo, bukan menjumlahkan kedua penunjuk terlebih dahulu. Menyebutkan hal ini dalam wawancara menunjukkan bahwa Anda memahami pertimbangan tingkat rendah.
# Safe mid calculation (important in Java/C++, good habit in Python too)
lo, hi = 0, 1_000_000_000
mid_unsafe = (lo + hi) // 2 # fine in Python
mid_safe = lo + (hi - lo) // 2 # same result, no overflow risk
print(mid_unsafe == mid_safe) # TrueBatas Inklusif vs Eksklusif
Salah satu bagian tersulit dari pencarian biner adalah memilih apakah hi menunjuk ke indeks valid terakhir (inklusif, hi = len(arr) - 1) atau satu posisi setelah akhir (eksklusif, hi = len(arr)). Konvensi yang berbeda memerlukan kondisi perulangan dan pembaruan batas yang berbeda.
Dengan batas inklusif, gunakan while lo <= hi dan perbarui hi = mid - 1. Dengan batas eksklusif, gunakan while lo < hi dan perbarui hi = mid. Mencampur konvensi merupakan sumber kesalahan yang paling umum dalam implementasi pencarian biner.
# Exclusive hi variant — useful for bisect-style lower-bound
def search_exclusive(arr, target):
lo, hi = 0, len(arr) # hi is one past last
while lo < hi: # strictly less than
mid = lo + (hi - lo) // 2
if arr[mid] < target:
lo = mid + 1
else:
hi = mid # NOT mid - 1
return lo if lo < len(arr) and arr[lo] == target else -1
print(search_exclusive([2, 4, 6, 8, 10], 6)) # 2Pencarian Biner Rekursif
Pencarian biner dapat ditulis secara rekursif dengan meneruskan batas lo dan hi yang telah diperbarui melalui tumpukan pemanggilan. Setiap pemanggilan rekursif mengurangi ruang pencarian menjadi setengahnya, sehingga kedalamannya adalah O(log n). Kasus dasarnya terjadi ketika lo > hi (tidak ditemukan) atau arr[mid] == target (ditemukan).
Versi iteratif lebih disukai dalam kode produksi karena menghindari overhead bingkai pemanggilan, tetapi versi rekursif menyampaikan struktur bagi-dan-taklukkan dengan lebih jelas di papan tulis.
def binary_search_rec(arr, target, lo, hi):
if lo > hi:
return -1
mid = lo + (hi - lo) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
return binary_search_rec(arr, target, mid + 1, hi)
else:
return binary_search_rec(arr, target, lo, mid - 1)
arr = [1, 3, 5, 7, 9, 11]
print(binary_search_rec(arr, 9, 0, len(arr) - 1)) # 4Kasus Tepi: Larik Kosong, Satu Elemen
Pencarian biner yang tangguh harus menangani kasus tepi tanpa mengalami kerusakan. Tiga kasus yang paling umum adalah: larik kosong (perulangan tidak pernah dijalankan dan -1 dikembalikan dengan benar), larik dengan satu elemen (mid sama dengan lo dan hi, sehingga satu perbandingan sudah cukup), serta sasaran di luar rentang (lo akhirnya melebihi hi dan -1 dikembalikan).
Selalu verifikasi implementasi Anda menggunakan masukan-masukan ini sebelum beralih ke pertanyaan lanjutan dalam wawancara.
def binary_search(arr, target):
lo, hi = 0, len(arr) - 1
while lo <= hi:
mid = lo + (hi - lo) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
lo = mid + 1
else:
hi = mid - 1
return -1
print(binary_search([], 5)) # -1 (empty)
print(binary_search([7], 7)) # 0 (single, found)
print(binary_search([7], 3)) # -1 (single, not found)
print(binary_search([1,3,5], 0)) # -1 (below range)
print(binary_search([1,3,5], 9)) # -1 (above range)Kompleksitas Waktu dan Ruang
Pencarian biner memiliki kompleksitas waktu O(log n) karena setiap perbandingan membagi dua ruang pencarian. Setelah k perbandingan, ruang yang tersisa adalah n/2^k; pencarian berakhir ketika nilai ini mencapai 1, sehingga k = log₂ n.
Kompleksitas ruang adalah O(1) untuk versi iteratif (hanya tiga variabel bilangan bulat) dan O(log n) untuk versi rekursif karena kedalaman tumpukan pemanggilan. Dalam wawancara, selalu nyatakan keduanya dan utamakan bentuk iteratif ketika ruang terbatas.
import math
for n in [10, 100, 1000, 1_000_000, 1_000_000_000]:
steps = math.ceil(math.log2(n + 1))
print(f'n={n:>12,} max comparisons={steps}')Mencari Kecocokan Persis vs Batas
Pencarian biner klasik mengembalikan sembarang indeks tempat sasaran berada. Namun, banyak soal wawancara meminta kemunculan pertama atau terakhir dari suatu sasaran. Untuk kasus tersebut, Anda harus terus mencari bahkan setelah menemukan kecocokan — alih-alih langsung mengembalikan hasil, persempit batas dan lanjutkan pencarian.
Saat mencari kemunculan pertama, setelah menemukan arr[mid] == target, catat indeks tersebut sebagai kandidat dan tetapkan hi = mid - 1. Untuk kemunculan terakhir, tetapkan lo = mid + 1.
def first_occurrence(arr, target):
lo, hi, result = 0, len(arr) - 1, -1
while lo <= hi:
mid = lo + (hi - lo) // 2
if arr[mid] == target:
result = mid
hi = mid - 1 # keep searching left
elif arr[mid] < target:
lo = mid + 1
else:
hi = mid - 1
return result
print(first_occurrence([1, 2, 2, 2, 3], 2)) # 1Menggunakan Modul bisect Python
Pustaka standar Python menyediakan bisect.bisect_left(arr, x) dan bisect.bisect_right(arr, x) untuk pencarian biner yang siap digunakan dalam produksi. bisect_left mengembalikan indeks paling kiri tempat x dapat disisipkan agar larik tetap terurut, yang secara efektif menemukan posisi pertama dengan arr[i] >= x.
Pewawancara mungkin mengizinkan Anda menggunakan bisect; selalu konfirmasikan terlebih dahulu. Memahami cara kerjanya di balik layar (yaitu pencarian biner O(log n)) tetap penting.
import bisect
arr = [1, 2, 2, 2, 3, 5]
print(bisect.bisect_left(arr, 2)) # 1 (first 2)
print(bisect.bisect_right(arr, 2)) # 4 (after last 2)
# Check if target exists
target = 3
idx = bisect.bisect_left(arr, target)
print(idx < len(arr) and arr[idx] == target) # TrueKesalahan Umum dalam Pencarian Biner
Tiga kesalahan menyebabkan sebagian besar masalah pencarian biner dalam wawancara. Pertama, kondisi perulangan yang salah: menggunakan < alih-alih <= dengan batas inklusif menyebabkan elemen terakhir yang tersisa terlewati. Kedua, pembaruan batas yang keliru: lupa menambahkan +1 atau -1 dapat menciptakan perulangan tanpa akhir ketika lo == hi. Ketiga, mengoperasikan larik yang belum terurut: pencarian biner hanya benar pada data yang terurut.
Sebelum menulis pencarian biner apa pun, nyatakan dengan lantang: 'Larik sudah terurut, batas saya inklusif, dan perulangan saya berjalan selama lo <= hi.'
# BUG: infinite loop when lo == hi because hi = mid never moves past lo
def buggy(arr, target):
lo, hi = 0, len(arr) - 1
while lo < hi: # should be lo <= hi for exact-match
mid = lo + (hi - lo) // 2
if arr[mid] < target:
lo = mid + 1
else:
hi = mid # stops, but never returns mid when found
return lo if arr[lo] == target else -1
print(buggy([1, 3, 5, 7], 7)) # 3 (works here by luck)
print(buggy([1, 3, 5, 7], 1)) # 0 (correct)
print(buggy([1, 3, 5, 7], 4)) # -1 (correct)Tips Wawancara untuk Pencarian Biner
Ketika melihat soal tentang larik terurut, fungsi yang naik secara monoton, atau ruang pencarian yang dapat dibagi dua, segera pertimbangkan pencarian biner. Dalam wawancara, jelaskan pemikiran Anda: 'Karena larik sudah terurut, saya dapat membuang separuh elemen pada setiap perbandingan, sehingga kompleksitasnya O(log n).'
Selalu verifikasi solusi Anda pada setidaknya tiga masukan: nilai di awal, nilai di akhir, dan nilai yang tidak ada. Menyatakan kompleksitas secara proaktif — 'waktu O(log n), ruang O(1)' — sebelum ditanya menunjukkan pemahaman dasar yang kuat.
Pemeriksaan Singkat
Uji pemahaman Anda tentang konsep Struktur Data & Algoritma — Persiapan Wawancara Pemrograman dari pelajaran ini.
Ringkasan Pelajaran
Dalam pelajaran ini Anda mempelajari: pencarian biner membagi dua ruang pencarian pada setiap langkah untuk mencapai waktu O(log n), konvensi batas inklusif menggunakan lo <= hi dengan pembaruan lo = mid+1 dan hi = mid-1, serta untuk menemukan kemunculan pertama/terakhir, Anda melanjutkan pencarian setelah menemukan kecocokan, bukan langsung mengembalikannya. Selanjutnya kita akan mempelajari penerapan pencarian biner pada larik yang diputar dan belum terurut.
Pertanyaan yang Sering Diajukan
Apakah pelajaran “Pencarian Biner Klasik: Kiri, Kanan, Tengah” gratis?
Ya — teks lengkap “Pencarian Biner Klasik: Kiri, Kanan, Tengah” gratis dibaca di sini di web. Untuk praktiknya secara interaktif (editor kode bawaan dan tutor AI 24/7) dan buka sisa kursus Coding Interview Prep, upgrade ke CoddyKit PRO. Kursus Coding Interview Prep mencakup 4 pelajaran total.
Apa yang akan aku pelajari di “Pencarian Biner Klasik: Kiri, Kanan, Tengah”?
Implementasikan pencarian biner secara iteratif dan rekursif, kuasai detail batas lo/hi agar tidak salah satu posisi, lalu verifikasi kebenarannya dengan input kasus tepi. Kamu berlatih Coding Interview Prep dengan kode praktik yang langsung kamu jalankan di browser, dan tutor AI 24/7 menjawab pertanyaanmu saat kamu mengerjakan pelajaran ini.
Apakah aku perlu pengalaman untuk memulai Coding Interview Prep?
Tidak diperlukan pengalaman sebelumnya. Coding Interview Prep di CoddyKit dirancang untuk pemula hingga pelajar tingkat lanjut, jadi kamu bisa memulai di sini atau dari awal dan belajar sesuai kecepatan kamu sendiri. Ini adalah pelajaran 1 dari 4.
Berapa lama pelajaran “Pencarian Biner Klasik: Kiri, Kanan, Tengah” memakan waktu?
Sebagian besar pelajaran CoddyKit memakan waktu sekitar 5–10 menit. Setiap pelajaran ringkas dan interaktif, jadi kamu membuat kemajuan stabil dan melanjutkan dari tempat kamu tinggalkan di web dan aplikasi.
Bisakah aku menulis dan menjalankan kode dalam pelajaran Coding Interview Prep ini?
Ya. Setiap pelajaran Coding Interview Prep menyertakan editor kode bawaan, jadi kamu menulis dan menjalankan kode nyata langsung di browser dan mendapatkan umpan balik AI instan — tidak diperlukan penyiapan lokal.
Semua pelajaran dalam kursus ini
- Pencarian Biner Klasik: Kiri, Kanan, Tengah
- Pencarian Biner pada Array Terputar dan Tak Terurut
- Batas Bawah dan Batas Atas
- Pencarian Biner pada Ruang Jawaban