Pencarian Biner pada Ruang Jawaban
Perlakukan rentang jawaban kontinu sebagai ruang pencarian untuk menyelesaikan masalah seperti waktu minimum menyelesaikan pekerjaan dan kapasitas pengiriman paket.
Pencarian Biner pada Ruang Jawaban adalah pelajaran DSA Interview Prep gratis di CoddyKit. Ini adalah pelajaran 4 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 DSA Interview Prep, dan progresmu tersinkronisasi di web dan aplikasi CoddyKit. Kursus DSA Interview Prep mencakup 4 pelajaran total.
Pencarian Biner pada Ruang Jawaban
Sebagian besar orang mengenal pencarian biner untuk menemukan nilai dalam larik terurut. Namun, pencarian biner menjadi jauh lebih kuat ketika diterapkan pada ruang kemungkinan jawaban. Alih-alih mencari dalam larik, Anda mencari dalam rentang numerik — misalnya, 'berapa jumlah hari minimum untuk mengirim semua paket?' — dan menggunakan fungsi pemeriksaan untuk menentukan apakah jawaban kandidat layak.
Teknik ini mengubah banyak masalah optimasi dari O(n²) atau lebih buruk menjadi O(n log(max_answer)).
Templat Ruang Jawaban
Templat ini memiliki tiga komponen. Pertama, tentukan rentang pencarian [lo, hi] yang mencakup semua jawaban yang valid. Kedua, tulis pemeriksaan kelayakan can_achieve(mid) yang mengembalikan True jika nilai mid dapat dicapai. Ketiga, lakukan pencarian biner pada [lo, hi]: jika can_achieve(mid), bergeraklah menuju jawaban yang lebih kecil (atau lebih besar); jika tidak, bergeraklah ke arah sebaliknya.
Sifat utamanya: fungsi kelayakan harus monoton — setelah suatu jawaban layak, semua nilai setelahnya juga layak (atau semua nilai di bawahnya tidak layak).
# Generic template
def answer_space_search(lo, hi, is_feasible):
result = hi # or lo, depending on direction
while lo <= hi:
mid = lo + (hi - lo) // 2
if is_feasible(mid):
result = mid
hi = mid - 1 # try to minimise further
else:
lo = mid + 1
return resultContoh: Kapasitas Pengiriman Paket
LeetCode 1011 'Kapasitas Pengiriman Paket dalam D Hari': diberikan daftar bobot dan D hari, tentukan kapasitas pengiriman minimum untuk mengirim semua paket sesuai urutan dalam D hari. Jawaban berada dalam [max(weights), sum(weights)]. Suatu kapasitas layak jika simulasi serakah dapat memuat semua paket dalam D hari. Pencarian biner atas rentang kapasitas menghasilkan waktu O(n log(jumlah)).
def shipWithinDays(weights, days):
def can_ship(capacity):
needed_days, current_load = 1, 0
for w in weights:
if current_load + w > capacity:
needed_days += 1
current_load = 0
current_load += w
return needed_days <= days
lo, hi = max(weights), sum(weights)
while lo < hi:
mid = lo + (hi - lo) // 2
if can_ship(mid):
hi = mid # feasible, try smaller
else:
lo = mid + 1 # not feasible, need more capacity
return lo
print(shipWithinDays([1,2,3,4,5,6,7,8,9,10], 5)) # 15
print(shipWithinDays([3,2,2,4,1,4], 3)) # 6Contoh: Koko Makan Pisang
LeetCode 875 'Koko Makan Pisang': Koko dapat makan K pisang per jam; ia ingin menghabiskan H tumpukan tepat dalam H jam, sambil meminimalkan K. Rentang pencarian adalah [1, max(piles)]. Pemeriksaannya: pada laju K, total jam = jumlah(ceil(tumpukan/K)), yang harus <= H. Kita melakukan pencarian biner untuk K terkecil yang memenuhi syarat ini.
import math
def minEatingSpeed(piles, h):
def can_finish(k):
return sum(math.ceil(p / k) for p in piles) <= h
lo, hi = 1, max(piles)
while lo < hi:
mid = lo + (hi - lo) // 2
if can_finish(mid):
hi = mid # feasible, try lower speed
else:
lo = mid + 1 # too slow
return lo
print(minEatingSpeed([3,6,7,11], 8)) # 4
print(minEatingSpeed([30,11,23,4,20], 5)) # 30Contoh: Jumlah Hari Minimum untuk Membuat Buket
LeetCode 1482 'Jumlah Minimum Hari untuk Membuat m Buket': Anda memerlukan m buket, masing-masing terdiri atas k bunga mekar yang berurutan. Bunga i mekar pada hari bloomDay[i]. Lakukan pencarian biner berdasarkan hari: rentangnya adalah [1, max(bloomDay)]. Pemeriksaan kelayakan menghitung bunga mekar yang berurutan dan menentukan apakah m buket dapat dibentuk. Sifat monoton: jika hari d berhasil, hari d+1 juga berhasil.
def minDays(bloomDay, m, k):
if m * k > len(bloomDay):
return -1 # impossible
def can_make(day):
bouquets = consecutive = 0
for bd in bloomDay:
if bd <= day:
consecutive += 1
if consecutive == k:
bouquets += 1
consecutive = 0
else:
consecutive = 0
return bouquets >= m
lo, hi = 1, max(bloomDay)
while lo < hi:
mid = lo + (hi - lo) // 2
if can_make(mid):
hi = mid
else:
lo = mid + 1
return lo
print(minDays([1,10,3,10,2], 3, 1)) # 3
print(minDays([1,10,3,10,2], 3, 2)) # -1Menentukan Rentang Pencarian
Memilih rentang [lo, hi] yang tepat sangat penting. lo harus merupakan jawaban minimum yang mungkin (misalnya, elemen minimum, 1, atau 0), sedangkan hi harus merupakan jawaban maksimum yang mungkin (misalnya, jumlah semua elemen, elemen maksimum, atau n). Menetapkan hi terlalu kecil membuat jawaban yang valid terlewat; menetapkannya terlalu besar tidak masalah karena pencarian biner tetap konvergen dalam O(log(hi - lo)) langkah.
# Choosing lo and hi for common problems:
# Capacity to ship: lo=max(weights), hi=sum(weights)
# Koko eating: lo=1, hi=max(piles)
# Square root: lo=1, hi=x
# Allocate books: lo=max(pages), hi=sum(pages)
def isqrt_bs(x):
if x < 2:
return x
lo, hi = 1, x
while lo < hi:
mid = lo + (hi - lo) // 2
if mid * mid <= x:
lo = mid + 1
else:
hi = mid
return lo - 1
for n in [0, 1, 4, 8, 9, 15, 16]:
print(f'isqrt({n}) = {isqrt_bs(n)}')Maksimalkan vs Minimalkan: Arah Pencarian Penting
Pencarian biner pada ruang jawaban memiliki dua varian. Minimalkan jawaban: ketika pemeriksaan berhasil, coba nilai yang lebih kecil (hi = mid); ketika gagal, coba nilai yang lebih besar (lo = mid + 1). Maksimalkan jawaban: ketika pemeriksaan berhasil, coba nilai yang lebih besar (lo = mid + 1, sambil menyimpan mid sebagai kandidat); ketika gagal, coba nilai yang lebih kecil (hi = mid - 1). Sebelum menulis kode, selalu pastikan arah pencarian yang digunakan.
# Maximise: largest x such that f(x) is feasible
def max_feasible(lo, hi, is_feasible):
result = lo - 1 # sentinel: no feasible answer found
while lo <= hi:
mid = lo + (hi - lo) // 2
if is_feasible(mid):
result = mid
lo = mid + 1 # try larger
else:
hi = mid - 1
return result
# Example: largest k such that k^2 <= 50
print(max_feasible(1, 50, lambda k: k * k <= 50)) # 7Alokasi Halaman Minimum (Masalah Klasik)
Diberikan n buku dengan larik halaman dan k siswa, alokasikan buku secara berurutan agar siswa yang membaca halaman terbanyak membaca sesedikit mungkin. Lakukan pencarian biner atas jawaban (maksimum minimum yang mungkin). Pemeriksaan kelayakan mengalokasikan buku kepada siswa secara serakah: ketika penambahan sebuah buku akan melebihi maksimum saat ini, berikan buku tersebut kepada siswa baru. Jika jumlah siswa yang diperlukan <= k, nilai maksimum tersebut dapat dicapai.
def allocate_min_pages(pages, k):
if k > len(pages):
return -1
def is_feasible(max_pages):
students, current = 1, 0
for p in pages:
if p > max_pages:
return False # single book exceeds limit
if current + p > max_pages:
students += 1
current = 0
current += p
return students <= k
lo, hi = max(pages), sum(pages)
while lo < hi:
mid = lo + (hi - lo) // 2
if is_feasible(mid):
hi = mid
else:
lo = mid + 1
return lo
print(allocate_min_pages([12, 34, 67, 90], 2)) # 113
print(allocate_min_pages([10, 20, 30, 40], 2)) # 60Analisis Kompleksitas Pencarian Ruang Jawaban
Kompleksitas waktunya adalah O(n × log(rentang)), dengan n sebagai biaya pemeriksaan kelayakan (biasanya pemindaian linear) dan rentang = hi - lo (ukuran ruang jawaban). Sebagai contoh, jika jumlah halaman mencapai 10⁹ dan pemeriksaan kelayakannya adalah O(n), total waktunya adalah O(n log 10⁹) ≈ O(30n), yang jauh lebih baik daripada brute force O(n²).
Kompleksitas ruang adalah O(1) untuk pencarian biner itu sendiri, ditambah ruang yang digunakan oleh pemeriksaan kelayakan.
import math
# Compare brute force vs answer-space binary search
# For sum = 10^9 and n = 10^5:
brute_ops = 10**9 # try every possible answer
bsearch_ops = 10**5 * math.log2(10**9) # n * log(range)
print(f'Brute force: {brute_ops:,.0f} operations')
print(f'Binary search: {bsearch_ops:,.0f} operations')
print(f'Speedup: {brute_ops / bsearch_ops:,.0f}x')Elemen ke-K Terkecil dalam Matriks Terurut
LeetCode 378 'Elemen Terkecil ke-K dalam Matriks Terurut': setiap baris dan kolom dalam matriks n×n telah diurutkan. Lakukan pencarian biner atas nilai jawaban dalam [matrix[0][0], matrix[n-1][n-1]]. Pemeriksaan kelayakan menghitung elemen <= nilai tengah dengan penunjuk yang dimulai dari sudut kiri bawah, dalam waktu O(n). Temukan nilai terkecil yang memiliki setidaknya k elemen <= nilai tengah.
def kthSmallest(matrix, k):
n = len(matrix)
def count_le(mid):
count, row, col = 0, n - 1, 0
while row >= 0 and col < n:
if matrix[row][col] <= mid:
count += row + 1
col += 1
else:
row -= 1
return count
lo, hi = matrix[0][0], matrix[n-1][n-1]
while lo < hi:
mid = lo + (hi - lo) // 2
if count_le(mid) >= k:
hi = mid
else:
lo = mid + 1
return lo
matrix = [[1,5,9],[10,11,13],[12,13,15]]
print(kthSmallest(matrix, 8)) # 13Mengenali Masalah Ruang Jawaban
Masalah yang cocok untuk pencarian biner ruang jawaban memiliki beberapa tanda umum: pertanyaannya meminta nilai minimum atau maksimum, jawabannya berada dalam rentang numerik yang terbatas, dan peningkatan (atau penurunan) nilai kandidat membuat kelayakan secara monoton membaik atau memburuk. Kata kunci klasiknya mencakup 'maksimum minimum yang mungkin', 'paling banyak k operasi', dan 'dalam d hari'.
Ketika melihat tanda-tanda ini, segera tentukan lo dan hi, tulis fungsi kelayakannya, lalu terapkan templat tersebut. Pendekatan terstruktur ini jarang gagal dalam wawancara.
Pemeriksaan Singkat
Uji pemahaman Anda tentang konsep Struktur Data & Algoritma — Persiapan Wawancara Pemrograman dari pelajaran ini.
Rangkuman Pelajaran
Dalam pelajaran ini Anda mempelajari: pencarian biner ruang jawaban berlaku ketika fungsi kelayakan bersifat monoton pada rentang numerik, templat menelusuri [lo, hi] dan menggunakan pemeriksaan pencapaian untuk membagi dua ruang pencarian, serta kompleksitas totalnya adalah O(n log(rentang)), dengan n sebagai biaya satu pemeriksaan kelayakan. Selanjutnya kita beralih ke daftar tertaut dan kelas simpul.
Pertanyaan yang Sering Diajukan
Apakah pelajaran “Pencarian Biner pada Ruang Jawaban” gratis?
Ya — teks lengkap “Pencarian Biner pada Ruang Jawaban” gratis dibaca di sini di web. Untuk praktiknya secara interaktif (editor kode bawaan dan tutor AI 24/7) dan buka sisa kursus DSA Interview Prep, upgrade ke CoddyKit PRO. Kursus DSA Interview Prep mencakup 4 pelajaran total.
Apa yang akan aku pelajari di “Pencarian Biner pada Ruang Jawaban”?
Perlakukan rentang jawaban kontinu sebagai ruang pencarian untuk menyelesaikan masalah seperti waktu minimum menyelesaikan pekerjaan dan kapasitas pengiriman paket. Kamu berlatih DSA 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 DSA Interview Prep?
Tidak diperlukan pengalaman sebelumnya. DSA 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 4 dari 4.
Berapa lama pelajaran “Pencarian Biner pada Ruang Jawaban” 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 DSA Interview Prep ini?
Ya. Setiap pelajaran DSA 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