Carian Binari pada Jawapan
Teka hasil dan semak kebolehlaksanaan.
Carian Binari pada 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.
Teka, Kemudian Sahkan
Kadang-kadang anda tidak boleh mengira jawapan secara terus, tetapi anda boleh menyemak tekaan. Carian binari terhadap jawapan menukarkan pengoptimuman yang sukar kepada semakan yang mudah.
# guess X, ask: is X feasible?Sifat Ajaib
Kaedah ini berfungsi apabila kebolehlaksanaan adalah monotonik: jika sesuatu nilai berfungsi, setiap nilai yang lebih besar atau lebih kecil juga berfungsi. Susunan itulah yang dicari.
# feasible(X) true => feasible(X+1) trueTetapkan Julat Jawapan
Kenal pasti jawapan paling kecil dan paling besar yang mungkin sebagai low dan high. Bagi kapasiti minimum, low ialah satu item dan high ialah jumlah keseluruhan.
low, high = max(weights), sum(weights)Tulis Ujian Kebolehlaksanaan
Teras kaedah ini ialah fungsi can(X) yang memulangkan benar jika tekaan X boleh dicapai. Biasanya fungsi ini berjalan dalam masa linear.
def can(cap):
# simulate and return True/False
...Contoh: Hantar dalam D Hari
Diberi kapasiti harian cap, isikan hari secara tamak dan kirakan bilangannya. can(cap) benar apabila bilangan hari tidak melebihi had D.
def can(cap):
days, load = 1, 0
for w in weights:
if load + w > cap:
days += 1; load = 0
load += w
return days <= DCari Kapasiti Minimum
Anda mahukan cap terkecil yang lulus. Ini ialah carian benar-pertama merentasi kapasiti, jadi gunakan semula templat high = mid.
while low < high:
mid = (low + high) // 2Kekalkan Separuh yang Boleh Dilaksanakan
Jika can(mid) benar, kapasiti yang lebih kecil mungkin masih berfungsi, jadi tetapkan high = mid. Jika tidak, naikkan had bawah dengan low = mid + 1.
if can(mid):
high = mid
else:
low = mid + 1Ambil Kira Belanjawan Masa
Jumlah kos ialah O(semakan x log julat). Semakan linear merentasi julat selebar satu bilion hanya memerlukan kira-kira 30 semakan, cukup pantas untuk had yang ketat.
# log2(1e9) is about 30 iterationsMaksimumkan, Bukan Minimumkan
Untuk mencari nilai boleh dilaksanakan yang terbesar, terbalikkan logiknya: cari nilai benar terakhir. Naikkan low apabila boleh dilaksanakan dan kurangkan high apabila tidak.
if can(mid):
low = mid
else:
high = mid - 1Jawapan Nilai Nyata
Bagi jawapan perpuluhan, ulang bilangan tetap seperti 100 kali dan bukannya menggunakan mid integer. Setiap pusingan membahagikan selang kepada separuh, lalu mencapai kejituan yang sangat tinggi dengan cepat.
for _ in range(100):
mid = (low + high) / 2Kenal Pasti Corak
Frasa seperti minimum terbesar, maksimum terkecil atau k terkecil yang berfungsi ialah petunjuk untuk mencari jawapan secara binari. Latih mata anda untuk mengenal pastinya.
# 'minimize the maximum' => search answerSemakan Ringkas
Tentukan masa yang sesuai untuk menggunakan carian binari terhadap jawapan.
Imbas Kembali: Cari Jawapan
Kini anda boleh menetapkan julat jawapan, menulis ujian kebolehlaksanaan dan mencari minimum atau maksimum secara binari. Masalah sukar menjadi proses teka dan sahkan. 🏆
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 pada Jawapan” percuma?
Ya — teks penuh “Carian Binari pada 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 pada Jawapan”?
Teka hasil dan semak kebolehlaksanaan. 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 pada 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 Tanpa Pepijat
- bisect_left dan bisect_right
- True Pertama: Carian Binari Predikat
- Carian Binari pada Jawapan