K1 · Modul 09
Pencarian biner dan dua penunjuk
48 langkah singkat, dari mudah sampai tantangan.
Level 1
Kenal
Level 2
Paham
Level 3
Terapkan
Level 4
Tantangan
Level 5
Pendalaman
Intinya
- Pencarian biner mencari batas: indeks pertama tempat predikat monoton berubah dari salah ke benar, dalam O(log n).
- Pakai rentang setengah terbuka
[lo, hi)dan invarian yang jelas; hampir semua galat satu-lebih berasal dari mencampur konvensi. - Pencarian biner juga bekerja pada jawaban (misalnya kapasitas terkecil yang cukup), asalkan predikatnya monoton.
- Dua penunjuk dan jendela geser menyelesaikan masalah pasangan dan rentang dalam satu lintasan, O(n).
- Di kode sungguhan pakai
bisect_left/bisect_right, dan pilih yang sesuai perlakuan data kembar.
Sebelum mulai
±4 jam.
Modul ini memakai materi di bawah. Belum yakin? Ulas dulu bagian yang disebut.
Hasil belajar: menulis pencarian biner batas bawah dan batas atas pada rentang setengah terbuka, lengkap dengan invarian dan bukti berhenti; memperbaiki galat satu-lebih; memakai pencarian biner pada jawaban; menyelesaikan masalah pasangan dan rentang dengan dua penunjuk dan jendela geser dalam waktu linear; serta memakai modul bisect, termasuk key=.
Proyek: Kurir Makmur langkah 9: cari_slot(jadwal, menit) (kontrak Proyek Kurir §3), indeks keberangkatan pertama yang tidak lebih awal dari menit.
Istilah di modul ini (20)
Ketuk istilah untuk melihat penjelasannya. Di materi, istilah bergaris titik membuka kartu yang sama. Semua istilah course
Bahan modul
Semua kode, latihan, dan data modul ini dalam satu zip, untuk dijalankan di laptop atau Google Colab.
- 32 contoh kode
- 9 berkas latihan + tes
- 1 berkas data
Lihat isi zip
- BACA-DULU.txt
- contoh_k1_09_26.py
- contoh_k1_09_51.py
- contoh_k1_09_67.py
- contoh_k1_09_154.py
- contoh_k1_09_190.py
- contoh_k1_09_244.py
- contoh_k1_09_294.py
- contoh_k1_09_625.py
- contoh_k1_09_662.py
- contoh_k1_09_696.py
- contoh_k1_09_731.py
- contoh_k1_09_764.py
- contoh_k1_09_790.py
- contoh_k1_09_874.py
- contoh_k1_09_914.py
- contoh_k1_09_1478.py
- contoh_k1_09_1570.py
- contoh_k1_09_1757.py
- contoh_k1_09_1799.py
- contoh_k1_09_1819.py
- contoh_k1_09_1842.py
- contoh_k1_09_1876.py
- contoh_k1_09_2233.py
- contoh_k1_09_2300.py
- contoh_k1_09_2327.py
- contoh_k1_09_2349.py
- contoh_k1_09_2375.py
- contoh_k1_09_2403.py
- contoh_k1_09_2612.py
- contoh_k1_09_2638.py
- contoh_k1_09_2681.py
- contoh_k1_09_2704.py
- test_k1_09_1.py
- test_k1_09_2.py
- test_k1_09_5.py
- test_k1_09_7.py
- test_k1_09_8.py
- test_k1_09_4.py
- test_k1_09_3.py
- test_k1_09_6.py
- test_k1_09_9.py
- peta.json