True Pertama: Binary Search Predicate
Mencari batas monoton ya/tidak
True Pertama: Binary Search Predicate adalah pelajaran Competitive Programming Academy gratis di CoddyKit. Ini adalah pelajaran 3 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.
Cari Batas Ya atau Tidak
Banyak masalah menyembunyikan predikat monoton: salah, salah, lalu selamanya benar. Pencarian biner dapat menemukan nilai benar pertama tanpa larik terurut.
# FFFFTTTT -> find first TArti Monoton
Predikat disebut monoton jika setelah berubah menjadi benar, nilainya tetap benar. Satu sifat inilah yang memungkinkan Anda mencari batas dengan pencarian biner.
def ok(x):
return x * x >= targetTentukan Ruang Jawaban
Pilih rentang yang pasti memuat batas tersebut. Tetapkan low sebagai kandidat terkecil dan high sebagai nilai yang pasti membuat ok bernilai benar.
low, high = 0, 10**9Uji Titik Tengah
Ambil mid dan panggil ok(mid). Hasil benar-salahnya memberi tahu separuh mana yang harus dipertahankan, persis seperti saat membandingkan nilai dalam pencarian biner biasa.
mid = (low + high) // 2
if ok(mid):
...Benar Berarti Mungkin Lebih Kecil
Jika ok(mid) bernilai benar, mid adalah jawaban yang valid, tetapi jawaban yang lebih kecil mungkin juga berhasil. Pertahankan mid dengan menetapkan high = mid, bukan mid - 1.
if ok(mid):
high = midSalah Berarti Bergerak Lebih Tinggi
Jika ok(mid) bernilai salah, batasnya berada di atas mid. Buang mid dan semua nilai di bawahnya dengan low = mid + 1.
else:
low = mid + 1Lakukan Perulangan Selama Low di Bawah High
Gunakan while low < high, bukan kondisi kurang dari atau sama dengan. Kedua penunjuk akan bertemu pada indeks benar pertama, lalu perulangan berhenti.
while low < high:
mid = (low + high) // 2Jawabannya adalah Low
Saat perulangan berakhir, low sama dengan high dan keduanya menunjuk ke nilai benar pertama. Kembalikan low sebagai batas yang Anda cari.
return low # first x where ok(x)Mengapa high = mid Berhasil
Karena mid mungkin merupakan jawaban, Anda tidak boleh melewatinya. Penggunaan high = mid mempertahankannya dalam rentang sekaligus tetap mempersempit rentang, sehingga kemajuan terjamin.
high = mid # mid stays a candidateContoh Akar Kuadrat Bilangan Bulat
Untuk menemukan x terbesar dengan x*x paling besar n, cari nilai benar pertama dari x*x > n, lalu mundur satu langkah. Pola ini dapat digunakan kembali.
def ok(x):
return x * x > n
# answer is found_index - 1Satu Templat, Banyak Masalah
Templat benar pertama ini menyelesaikan banyak tugas: nilai minimum yang layak, indeks paling kiri, dan kapasitas terkecil. Pelajari sekali, lalu gunakan kembali di mana saja.
# low<high, ok->high=mid, else low=mid+1Pemeriksaan Singkat
Tentukan langkah yang mempertahankan kandidat tetap hidup.
Ringkasan: Nilai Benar Pertama Ditemukan
Sekarang Anda dapat mengubah masalah menjadi predikat monoton dan mencari batasnya dengan pencarian biner. high = mid serta while low < high merupakan pola yang aman. 🧭
Pertanyaan yang Sering Diajukan
Apakah pelajaran “True Pertama: Binary Search Predicate” gratis?
Ya — teks lengkap “True Pertama: Binary Search Predicate” 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 “True Pertama: Binary Search Predicate”?
Mencari batas monoton ya/tidak 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 3 dari 4.
Berapa lama pelajaran “True Pertama: Binary Search Predicate” 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
- Binary Search Klasik Tanpa Bug
- bisect_left dan bisect_right
- True Pertama: Binary Search Predicate
- Binary Search pada Jawaban