bisect_left dan bisect_right
Menemukan titik penyisipan dalam list terurut
bisect_left dan bisect_right adalah pelajaran Competitive Programming Academy gratis di CoddyKit. Ini adalah pelajaran 2 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.
Mencari Tanpa Kerangka Berulang
Modul Python bisect menyediakan pencarian biner teruji untuk daftar terurut. Tanpa perulangan yang ditulis manual, tidak ada kesalahan selisih satu yang perlu diperbaiki.
import bisectTitik Penyisipan, Bukan Nilai Benar-Salah
Alih-alih benar atau salah, bisect mengembalikan sebuah indeks tempat suatu nilai akan disisipkan agar daftar tetap terurut. Indeks itulah sumber kekuatan sebenarnya.
a = [1, 3, 3, 3, 7]bisect_left Condong ke Kiri
bisect_left mengembalikan posisi pertama tempat nilai tersebut dapat ditempatkan. Untuk duplikat, hasilnya berada sebelum semua elemen yang sama, tidak pernah sesudahnya.
bisect.bisect_left(a, 3) # 1bisect_right Condong ke Kanan
bisect_right mengembalikan posisi tepat setelah elemen terakhir yang sama. Jika ada duplikat, hasilnya berada setelah setiap nilai yang cocok.
bisect.bisect_right(a, 3) # 4Hitung Elemen yang Sama
Kurangkan kedua hasil tersebut untuk menghitung duplikat suatu nilai dalam O(log n). bisect_right dikurangi bisect_left menghasilkan tepat jumlah kemunculannya.
lo = bisect.bisect_left(a, 3)
hi = bisect.bisect_right(a, 3)
print(hi - lo) # 3Apakah Nilainya Ada?
Untuk memeriksa keanggotaan, dapatkan i dari bisect_left dan pastikan a[i] sama dengan target. Pastikan terlebih dahulu bahwa i belum mencapai panjang daftar.
i = bisect.bisect_left(a, x)
found = i < len(a) and a[i] == xElemen Pertama yang Setidaknya x
bisect_left juga menemukan elemen pertama yang lebih besar atau sama dengan x. Indeks tersebut langsung menunjuk ke jawaban batas bawah Anda.
i = bisect.bisect_left(a, x) # first >= xElemen Pertama yang Lebih Besar Secara Ketat
Memerlukan elemen pertama yang benar-benar lebih besar daripada x? bisect_right memberikan indeks tersebut secara langsung, sebagai pasangan batas atasnya.
i = bisect.bisect_right(a, x) # first > xSisipkan dan Pertahankan Urutan
insort menemukan tempatnya dan menyisipkan nilai dalam satu pemanggilan, sehingga daftar tetap terurut. Ini berguna saat Anda membangun struktur terurut sambil berjalan.
bisect.insort(a, 5) # a stays sortedCari di Dalam Jendela
Argumen opsional lo dan hi membatasi pencarian pada suatu potongan. Dengan begitu, Anda tidak perlu menyalin data saat hanya memerlukan subrentang.
bisect.bisect_left(a, x, 2, 5)Gunakan Kunci melalui Daftar Bantuan
bisect membandingkan elemen secara keseluruhan. Jadi, untuk mencari berdasarkan suatu atribut, buat daftar paralel yang hanya berisi kunci tersebut, lalu gunakan bisect pada daftar itu.
keys = [p[0] for p in pairs]
i = bisect.bisect_left(keys, target)Pemeriksaan Singkat
Bernalarlah tentang duplikat dan titik penyisipan.
Ringkasan: Menguasai Bisect
Sekarang Anda dapat menemukan titik penyisipan, menghitung duplikat, dan menemukan batas bawah serta batas atas dalam waktu logaritmik. Gunakan bisect sebelum menulis perulangan. ✨
Pertanyaan yang Sering Diajukan
Apakah pelajaran “bisect_left dan bisect_right” gratis?
Ya — teks lengkap “bisect_left dan bisect_right” 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 “bisect_left dan bisect_right”?
Menemukan titik penyisipan dalam list terurut 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 2 dari 4.
Berapa lama pelajaran “bisect_left dan bisect_right” 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