PricingLoginStart free
Competitive Programming Academy · Pelajaran

Binary Search pada Jawaban

Menebak hasil dan memeriksa kelayakannya

Pelajaran 4 dari 413 langkah

Binary Search pada Jawaban adalah pelajaran Competitive Programming Academy 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 Competitive Programming Academy, dan progresmu tersinkronisasi di web dan aplikasi CoddyKit. Kursus Competitive Programming Academy mencakup 4 pelajaran total.

Tebak, Lalu Verifikasi

Terkadang Anda tidak dapat menghitung jawaban secara langsung, tetapi dapat memeriksa tebakan. Pencarian biner pada jawaban mengubah optimasi yang sulit menjadi pemeriksaan yang mudah.

# guess X, ask: is X feasible?

Sifat Ajaibnya

Metode ini bekerja ketika kelayakan bersifat monoton: jika suatu nilai berhasil, setiap nilai yang lebih besar atau lebih kecil juga berhasil. Urutan itulah yang Anda cari.

# feasible(X) true => feasible(X+1) true

Batasi Rentang Jawaban

Identifikasi jawaban terkecil dan terbesar yang mungkin sebagai low dan high. Untuk kapasitas minimum, low adalah satu item dan high adalah jumlah total.

low, high = max(weights), sum(weights)

Tulis Pemeriksaan Kelayakan

Inti metode ini adalah fungsi can(X) yang mengembalikan benar jika tebakan X dapat dicapai. Fungsi ini biasanya berjalan dalam waktu linear.

def can(cap):
    # simulate and return True/False
    ...

Contoh: Mengirim dalam D Hari

Dengan kapasitas harian cap, isilah setiap hari secara rakus dan hitung jumlah harinya. can(cap) bernilai benar jika jumlah hari tetap berada dalam batas D.

def can(cap):
    days, load = 1, 0
    for w in weights:
        if load + w > cap:
            days += 1; load = 0
        load += w
    return days <= D

Cari Kapasitas Minimum

Anda menginginkan cap terkecil yang berhasil. Ini adalah pencarian benar pertama atas kapasitas, jadi gunakan kembali templat high = mid.

while low < high:
    mid = (low + high) // 2

Pertahankan Separuh yang Layak

Jika can(mid) bernilai benar, kapasitas yang lebih kecil mungkin masih berhasil, jadi tetapkan high = mid. Jika tidak, naikkan batas bawah dengan low = mid + 1.

if can(mid):
    high = mid
else:
    low = mid + 1

Perhatikan Anggaran Waktu

Total biayanya adalah O(check x log range). Pemeriksaan linear pada rentang selebar satu miliar hanya memerlukan sekitar 30 pemeriksaan, cukup cepat untuk batas yang ketat.

# log2(1e9) is about 30 iterations

Maksimalkan, Bukan Minimalkan

Untuk menemukan nilai layak yang terbesar, balik logikanya: cari nilai benar terakhir. Naikkan low saat nilai layak dan kurangi high saat tidak layak.

if can(mid):
    low = mid
else:
    high = mid - 1

Jawaban Bernilai Riil

Untuk jawaban pecahan, lakukan perulangan dengan jumlah tetap seperti 100 kali, bukan menggunakan mid bilangan bulat. Setiap putaran membagi dua interval dan dengan cepat mencapai presisi yang sangat tinggi.

for _ in range(100):
    mid = (low + high) / 2

Kenali Polanya

Frasa seperti minimum terbesar, maksimum terkecil, atau k terkecil yang berhasil merupakan tanda untuk melakukan pencarian biner pada jawaban. Latih kepekaan Anda untuk mengenalinya.

# 'minimize the maximum' => search answer

Pemeriksaan Singkat

Tentukan kapan pencarian biner pada jawaban dapat diterapkan.

Jawab di pelajaran interaktif

Ringkasan: Cari Jawabannya

Sekarang Anda dapat membatasi jawaban, menulis pemeriksaan kelayakan, dan melakukan pencarian biner untuk menemukan nilai minimum atau maksimum. Masalah sulit berubah menjadi tebak-dan-verifikasi. 🏆

Gratis untuk memulai

Belajar Python dengan tutor AI — gratis

Tulis dan jalankan kode asli di browser kamu, dapatkan bantuan instan dari tutor AI 24/7, dan lanjutkan di mana kamu tinggalkan di web atau aplikasi.

Kursus
30
Pelajaran
120
Mulai belajar gratisLihat kursus lengkapnya

Pertanyaan yang Sering Diajukan

Apakah pelajaran “Binary Search pada Jawaban” gratis?

Ya — teks lengkap “Binary Search pada Jawaban” gratis dibaca di sini di web. Untuk praktiknya secara interaktif (editor kode bawaan dan tutor AI 24/7) dan buka sisa kursus Competitive Programming Academy, upgrade ke CoddyKit PRO. Kursus Competitive Programming Academy mencakup 4 pelajaran total.

Apa yang akan aku pelajari di “Binary Search pada Jawaban”?

Menebak hasil dan memeriksa kelayakannya Kamu berlatih Competitive Programming Academy 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 Competitive Programming Academy?

Tidak diperlukan pengalaman sebelumnya. Competitive Programming Academy 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 “Binary Search pada 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 Competitive Programming Academy ini?

Ya. Setiap pelajaran Competitive Programming Academy 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

  1. Binary Search Klasik Tanpa Bug
  2. bisect_left dan bisect_right
  3. True Pertama: Binary Search Predicate
  4. Binary Search pada Jawaban
← Kembali ke Competitive Programming Academy