Carian Binari Ruang Jawapan
Anggap julat jawapan berterusan sebagai ruang carian untuk menyelesaikan masalah seperti minimum-time-to-complete-jobs dan capacity-to-ship-packages.
Carian Binari Ruang Jawapan ialah pelajaran Persediaan Temu Duga Pengaturcaraan percuma di CoddyKit. Ini ialah pelajaran 4 daripada 4. Anda boleh membaca keseluruhan pelajaran di bawah secara percuma — kemudian berlatih secara praktikal dalam pelayar menggunakan penyunting kod terbina dalam dan tutor kecerdasan buatan 24/7. Pelajaran ini merupakan sebahagian daripada laluan pembelajaran Persediaan Temu Duga Pengaturcaraan, dan kemajuan anda disegerakkan merentas web serta aplikasi CoddyKit. Kursus Persediaan Temu Duga Pengaturcaraan merangkumi sejumlah 4 pelajaran.
Carian Binari dalam Ruang Jawapan
Kebanyakan orang mengenali carian binari untuk mencari nilai dalam tatasusunan diisih. Namun, carian binari menjadi lebih berkuasa apabila digunakan pada ruang jawapan yang mungkin. Daripada mencari dalam tatasusunan, anda mencari julat angka — contohnya, 'apakah bilangan hari minimum untuk menghantar semua pakej?' — dan menggunakan fungsi semakan untuk menentukan sama ada jawapan calon boleh dilaksanakan.
Teknik ini menukar banyak masalah pengoptimuman daripada O(n²) atau lebih buruk kepada O(n log(max_answer)).
Templat Ruang Jawapan
Templat ini mempunyai tiga komponen. Pertama, tentukan julat carian [lo, hi] yang merangkumi semua jawapan sah. Kedua, tulis semakan kebolehlaksanaan can_achieve(mid) yang mengembalikan benar jika nilai mid boleh dicapai. Ketiga, lakukan carian binari pada [lo, hi]: jika can_achieve(mid), bergerak ke arah jawapan yang lebih kecil (atau lebih besar); jika tidak, bergerak ke arah yang bertentangan.
Sifat utama: fungsi kebolehlaksanaan mestilah monoton — sebaik sahaja sesuatu jawapan boleh dilaksanakan, semua nilai selepasnya juga boleh dilaksanakan (atau semua nilai di bawahnya tidak boleh dilaksanakan).
# 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: Kapasiti Menghantar Bungkusan
LeetCode 1011 'Kapasiti Menghantar Bungkusan dalam D Hari': diberikan senarai berat dan D hari, tentukan kapasiti penghantaran minimum untuk menghantar semua bungkusan mengikut urutan dalam masa D hari. Jawapannya berada dalam [max(weights), sum(weights)]. Sesuatu kapasiti boleh dilaksanakan jika simulasi tamak dapat memuatkan semua bungkusan dalam masa D hari. Carian binari pada julat kapasiti memberikan masa 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 boleh makan K biji pisang sejam; dia mahu menghabiskan H timbunan dalam tepat H jam sambil meminimumkan K. Julat carian ialah [1, max(piles)]. Semakannya: pada kadar K, jumlah jam = jumlah(ceil(timbunan/K)), yang mestilah <= H. Kita melakukan carian binari untuk mencari 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: Bilangan Hari Minimum untuk Membuat Jambangan
LeetCode 1482 'Bilangan Minimum Hari untuk Membuat m Jambangan': anda memerlukan m jambangan, setiap satunya terdiri daripada k bunga yang mekar berturutan. Bunga i mekar pada hari bloomDay[i]. Lakukan carian binari berdasarkan hari: julatnya ialah [1, maksimum bloomDay]. Semakan kebolehlaksanaan mengira bunga yang mekar berturutan dan menentukan sama ada m jambangan boleh dibentuk. Sifat monotonik: jika hari d berjaya, hari d+1 juga berjaya.
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)) # -1Mengenal Pasti Julat Carian
Memilih julat [lo, hi] yang betul amat penting. lo hendaklah merupakan jawapan minimum yang mungkin (contohnya, elemen minimum, 1 atau 0), manakala hi hendaklah merupakan jawapan maksimum yang mungkin (contohnya, jumlah semua elemen, elemen maksimum atau n). Jika hi ditetapkan terlalu kecil, jawapan yang sah akan terlepas; jika ditetapkan terlalu besar, itu tidak mengapa kerana carian binari masih akan menumpu 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)}')Maksimumkan berbanding Minimumkan: Arah Penting
Carian binari ruang jawapan mempunyai dua bentuk. Minimumkan jawapan: apabila semakan berjaya, cuba nilai yang lebih kecil (hi = mid); apabila semakan gagal, cuba nilai yang lebih besar (lo = mid + 1). Maksimumkan jawapan: apabila semakan berjaya, cuba nilai yang lebih besar (lo = mid + 1, sambil menyimpan mid sebagai calon); apabila semakan gagal, cuba nilai yang lebih kecil (hi = mid - 1). Sentiasa jelaskan arah carian sebelum menulis kod.
# 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)) # 7Peruntukan Halaman Minimum (Masalah Klasik)
Diberikan n buah buku yang mengandungi jumlah halaman tertentu dan k orang pelajar, peruntukkan buku secara bersebelahan supaya pelajar yang membaca halaman paling banyak membaca sesedikit mungkin. Lakukan carian binari pada jawapan (maksimum minimum yang mungkin). Semakan kebolehlaksanaan memperuntukkan buku kepada pelajar secara tamak: apabila penambahan sebuah buku akan melebihi maksimum semasa, berikan buku itu kepada pelajar baharu. Jika bilangan pelajar yang diperlukan <= k, maksimum tersebut boleh 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 Kerumitan Carian Ruang Jawapan
Kerumitan masa ialah O(n × log(julat)), dengan n ialah kos semakan kebolehlaksanaan (biasanya imbasan linear) dan julat = hi - lo (saiz ruang jawapan). Sebagai contoh, jika jumlah halaman ialah 10⁹ dan semakan kebolehlaksanaan ialah O(n), jumlah masa ialah O(n log 10⁹) ≈ O(30n), yang jauh lebih baik daripada O(n²) secara kekerasan.
Kerumitan ruang ialah O(1) untuk carian binari itu sendiri, ditambah dengan ruang yang digunakan oleh semakan kebolehlaksanaan.
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 Tersusun
LeetCode 378 'Elemen Ke-k Terkecil dalam Matriks Tersusun': setiap baris dan lajur matriks n×n disusun. Lakukan carian binari pada nilai jawapan dalam [matrix[0][0], matrix[n-1][n-1]]. Semakan kebolehlaksanaan mengira elemen <= mid menggunakan penuding yang bermula dari penjuru kiri bawah, dalam masa O(n). Cari nilai terkecil yang mempunyai sekurang-kurangnya 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 Jawapan
Masalah yang sesuai untuk carian binari ruang jawapan mempunyai petunjuk umum: soalan meminta nilai minimum atau maksimum, jawapan berada dalam julat angka yang terhad, dan peningkatan (atau pengurangan) jawapan calon menjadikan kebolehlaksanaan secara monotonik lebih baik atau lebih buruk. Kata kunci klasik termasuk 'maksimum minimum yang mungkin', 'paling banyak k operasi' dan 'dalam d hari'.
Apabila anda mengenal pasti petunjuk ini, tentukan had bawah dan had atas dengan segera, tulis fungsi kebolehlaksanaan dan gunakan templat tersebut. Pendekatan berstruktur ini jarang gagal dalam temu duga.
Semakan Ringkas
Uji pemahaman anda tentang konsep Struktur Data & Algoritma — Persediaan Temu Duga Pengekodan daripada pelajaran ini.
Ulang Kaji Pelajaran
Dalam pelajaran ini anda telah mempelajari bahawa: carian binari ruang jawapan digunakan apabila fungsi kebolehlaksanaan adalah monotonik merentasi julat angka, templat mencari julat daripada had bawah hingga had atas dan menggunakan semakan untuk menentukan sama ada jawapan boleh dicapai bagi membahagikan ruang carian kepada dua, dan kerumitan keseluruhan ialah O(n log(julat)), dengan n ialah kos satu semakan kebolehlaksanaan. Seterusnya kita akan beralih kepada senarai terpaut dan kelas nod.
Pelajari Persediaan Temu Duga Pengaturcaraan dengan tutor kecerdasan buatan — percuma
Tulis dan jalankan kod sebenar dalam pelayar anda, dapatkan bantuan segera daripada tutor kecerdasan buatan yang tersedia 24/7, dan sambung semula dari tempat anda berhenti di web atau dalam aplikasi.
- Kursus
- 90
- Pelajaran
- 360
Soalan Lazim
Adakah pelajaran “Carian Binari Ruang Jawapan” percuma?
Ya — teks penuh “Carian Binari Ruang Jawapan” boleh dibaca secara percuma di web ini. Untuk berlatih secara interaktif menggunakan penyunting kod terbina dalam dan tutor kecerdasan buatan 24/7, serta membuka kunci baki kursus Persediaan Temu Duga Pengaturcaraan, tingkat taraf kepada CoddyKit PRO. Kursus Persediaan Temu Duga Pengaturcaraan merangkumi sejumlah 4 pelajaran.
Apakah yang akan saya pelajari dalam “Carian Binari Ruang Jawapan”?
Anggap julat jawapan berterusan sebagai ruang carian untuk menyelesaikan masalah seperti minimum-time-to-complete-jobs dan capacity-to-ship-packages. Anda berlatih Persediaan Temu Duga Pengaturcaraan menggunakan kod praktikal yang dijalankan terus dalam pelayar, manakala tutor kecerdasan buatan 24/7 menjawab soalan anda semasa anda mengikuti pelajaran.
Adakah saya memerlukan pengalaman untuk memulakan Persediaan Temu Duga Pengaturcaraan?
Tiada pengalaman terdahulu diperlukan. Pembelajaran Persediaan Temu Duga Pengaturcaraan di CoddyKit disusun untuk pelajar daripada peringkat pemula hingga lanjutan, jadi anda boleh bermula di sini atau dari awal dan belajar mengikut kadar anda sendiri. Ini ialah pelajaran 4 daripada 4.
Berapa lamakah pelajaran “Carian Binari Ruang Jawapan” diambil?
Kebanyakan pelajaran CoddyKit mengambil masa kira-kira 5–10 minit. Setiap pelajaran ringkas dan interaktif, jadi anda boleh membuat kemajuan secara berterusan dan menyambung tepat dari tempat anda berhenti di web atau aplikasi.
Bolehkah saya menulis dan menjalankan kod dalam pelajaran Persediaan Temu Duga Pengaturcaraan ini?
Ya. Setiap pelajaran Persediaan Temu Duga Pengaturcaraan menyertakan penyunting kod terbina dalam, jadi anda boleh menulis dan menjalankan kod sebenar terus dalam pelayar serta menerima maklum balas kecerdasan buatan serta-merta — tanpa memerlukan persediaan setempat.
Semua pelajaran dalam kursus ini
- Carian Binari Klasik: Kiri, Kanan, Tengah
- Carian Binari pada Tatasusunan Diputar dan Tidak Tersusun
- Had Bawah dan Had Atas
- Carian Binari Ruang Jawapan