Pada data yang terurut, Anda dapat menemukan suatu nilai tanpa memindai seluruhnya: lihat item di tengah, lalu pertahankan hanya separuh tempat nilai itu pasti berada. Setiap langkah membagi dua rentang, sehingga sejuta item hanya butuh sekitar 20 langkah (O(log n)).
Versi manualnya menyimpan dua batas, lo dan hi, dan menggeser salah satunya melewati mid setiap kali: lo = mid + 1 atau hi = mid - 1. Jika Anda memakai lo = mid, rentang bisa macet dan perulangan berjalan selamanya.
Modul bisect melakukannya untuk Anda:
bisect_left(a, x): posisi pertama tempat x bisa diletakkan, sebelum nilai yang sama.
bisect_right(a, x): posisi setelah semua nilai yang sama.
bisect_right(a, hi) - bisect_left(a, lo) menghitung nilai di antara lo dan hi.
Beginilah lapisan pajak, rentang harga, dan pencarian "hari pertama kita mencapai target" dikerjakan.
Keluaran: (1, 3, 3). Ada tiga harga dari 9 sampai 12.