Batas Bawah dan Batas Atas
Implementasikan bisect_left dan bisect_right dari awal, lalu gunakan keduanya untuk menemukan posisi pertama dan terakhir suatu nilai target.
Batas Bawah dan Batas Atas adalah pelajaran DSA Interview Prep 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 DSA Interview Prep, dan progresmu tersinkronisasi di web dan aplikasi CoddyKit. Kursus DSA Interview Prep mencakup 4 pelajaran total.
Apa Itu Batas Bawah dan Batas Atas?
Batas bawah suatu nilai sasaran dalam larik terurut adalah indeks elemen pertama yang lebih besar dari atau sama dengan sasaran (sering disebut bisect_left). Batas atas adalah indeks elemen pertama yang benar-benar lebih besar dari sasaran (bisect_right). Bersama-sama, keduanya membatasi setiap kemunculan sasaran dan memungkinkan kueri rentang dalam O(log n).
Kedua operasi ini menjadi dasar bagi banyak masalah wawancara: menghitung kemunculan, menemukan rentang, menentukan posisi penyisipan, dan lainnya.
arr = [1, 2, 2, 2, 3, 5]
# lower bound of 2 => index 1 (first element >= 2)
# upper bound of 2 => index 4 (first element > 2)
# occurrences of 2 => upper - lower = 4 - 1 = 3
print('lower bound of 2:', 1)
print('upper bound of 2:', 4)
print('count of 2:', 4 - 1)Mengimplementasikan Batas Bawah (bisect_left)
bisect_left(arr, x) mengembalikan indeks paling kiri i sehingga arr[i] >= x, atau len(arr) jika semua elemen lebih kecil. Implementasinya menggunakan batas atas eksklusif: hi = len(arr), kondisi perulangan lo < hi, dan pembaruan hi = mid ketika arr[mid] >= x. Dengan demikian, jawaban menyatu pada posisi valid paling kiri.
def bisect_left(arr, x):
lo, hi = 0, len(arr)
while lo < hi:
mid = lo + (hi - lo) // 2
if arr[mid] < x:
lo = mid + 1
else:
hi = mid # arr[mid] >= x, so potential answer
return lo # lo == hi == insertion point
arr = [1, 2, 2, 2, 3, 5]
print(bisect_left(arr, 2)) # 1
print(bisect_left(arr, 0)) # 0 (before all)
print(bisect_left(arr, 6)) # 6 (after all)
print(bisect_left(arr, 3)) # 4Mengimplementasikan Batas Atas (bisect_right)
bisect_right(arr, x) mengembalikan indeks paling kiri i sehingga arr[i] > x. Hanya satu baris yang berbeda dari bisect_left: kondisinya berubah dari arr[mid] < x menjadi arr[mid] <= x. Ketika arr[mid] <= x, jawaban berada tepat di sebelah kanan mid, jadi kita menetapkan lo = mid + 1; jika tidak, kita mempersempit dari sisi kanan.
def bisect_right(arr, x):
lo, hi = 0, len(arr)
while lo < hi:
mid = lo + (hi - lo) // 2
if arr[mid] <= x:
lo = mid + 1 # arr[mid] <= x, so answer is strictly right
else:
hi = mid
return lo
arr = [1, 2, 2, 2, 3, 5]
print(bisect_right(arr, 2)) # 4
print(bisect_right(arr, 0)) # 0
print(bisect_right(arr, 5)) # 6
print(bisect_right(arr, 4)) # 5Menghitung Kemunculan dengan Kedua Batas
Untuk menghitung kemunculan sasaran dalam larik terurut dalam O(log n), terapkan kedua batas: count = bisect_right(arr, target) - bisect_left(arr, target). Jika jumlahnya 0, sasaran tidak ada. Metode ini jauh lebih cepat daripada pemindaian linear dan merupakan pendekatan standar untuk kueri frekuensi pada data terurut.
import bisect
def count_occurrences(arr, target):
left = bisect.bisect_left(arr, target)
right = bisect.bisect_right(arr, target)
return right - left
arr = [1, 2, 2, 2, 3, 3, 5]
print(count_occurrences(arr, 2)) # 3
print(count_occurrences(arr, 3)) # 2
print(count_occurrences(arr, 4)) # 0
print(count_occurrences(arr, 1)) # 1Menemukan Posisi Pertama dan Terakhir Sasaran
LeetCode 34 'Menemukan Posisi Pertama dan Terakhir Elemen dalam Larik Terurut' meminta Anda mengembalikan [first_idx, last_idx] dalam O(log n). Posisi pertama adalah bisect_left(arr, target) — tetapi hanya jika arr[result] == target. Posisi terakhir adalah bisect_right(arr, target) - 1. Jika salah satu pemeriksaan gagal, kembalikan [-1, -1].
import bisect
def search_range(nums, target):
left = bisect.bisect_left(nums, target)
if left == len(nums) or nums[left] != target:
return [-1, -1]
right = bisect.bisect_right(nums, target) - 1
return [left, right]
print(search_range([5,7,7,8,8,10], 8)) # [3, 4]
print(search_range([5,7,7,8,8,10], 6)) # [-1, -1]
print(search_range([], 0)) # [-1, -1]Posisi Penyisipan (LeetCode 35)
LeetCode 35 'Posisi Penyisipan Sasaran' menanyakan: di mana sasaran akan disisipkan agar larik tetap terurut? Jawabannya tepat bisect_left(arr, target). Jika sasaran ada, bisect_left mengembalikan indeksnya. Jika sasaran tidak ada, bisect_left mengembalikan indeks tempat sasaran tersebut akan disisipkan. Tidak diperlukan penanganan khusus — fungsi yang sama menangani kedua situasi.
import bisect
def searchInsert(nums, target):
return bisect.bisect_left(nums, target)
print(searchInsert([1,3,5,6], 5)) # 2 (exists at index 2)
print(searchInsert([1,3,5,6], 2)) # 1 (would insert between 1 and 3)
print(searchInsert([1,3,5,6], 7)) # 4 (would append at end)
print(searchInsert([1,3,5,6], 0)) # 0 (would prepend)Perbedaan antara bisect_left dan bisect_right
Jika tidak ada duplikat, bisect_left dan bisect_right mengembalikan indeks yang sama. Perbedaannya hanya penting ketika sasaran muncul berkali-kali. bisect_left menunjuk ke salinan pertama; bisect_right menunjuk ke posisi satu setelah salinan terakhir. Selalu pilih berdasarkan apakah Anda ingin menyisipkan sebelum salinan yang sudah ada (kiri) atau sesudahnya (kanan).
import bisect
arr = [1, 2, 2, 2, 3]
# Insert a new 2 before all existing 2s
print(bisect.bisect_left(arr, 2)) # 1
# Insert a new 2 after all existing 2s
print(bisect.bisect_right(arr, 2)) # 4
# For a value not in array, both give same insertion point
print(bisect.bisect_left(arr, 2.5)) # 4
print(bisect.bisect_right(arr, 2.5)) # 4Menerapkan Batas pada Kueri Frekuensi Terurut
Jika Anda perlu menjawab banyak kueri frekuensi rentang pada larik terurut secara efisien, hitung larik terurut tersebut sekali dan gunakan pencarian batas untuk setiap kueri. Setiap kueri menjawab pertanyaan 'berapa banyak elemen yang berada dalam [lo, hi]?' dalam O(log n), bukan O(n). Pola ini muncul dalam masalah tentang menghitung elemen dalam rentang nilai setelah pengurutan.
import bisect
def count_in_range(arr, lo, hi):
'''Count elements in arr with lo <= val <= hi. arr must be sorted.'''
left = bisect.bisect_left(arr, lo)
right = bisect.bisect_right(arr, hi)
return right - left
arr = sorted([3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5])
print(arr) # [1,1,2,3,3,4,5,5,5,6,9]
print(count_in_range(arr, 3, 5)) # 6 (3,3,4,5,5,5)
print(count_in_range(arr, 1, 2)) # 3 (1,1,2)Pencarian Biner dengan Kunci Kustom
Terkadang kunci pencarian bukanlah nilai yang disimpan, melainkan properti turunan. Modul bisect Python tidak mendukung fungsi kunci secara langsung, tetapi Anda dapat melakukan pencarian biner secara manual dengan menerapkan kunci tersebut di dalam perulangan. Pola ini muncul saat mencari daftar objek berdasarkan salah satu atributnya.
# Binary search on a list of (score, name) tuples by score
def lower_bound_by_score(records, min_score):
lo, hi = 0, len(records)
while lo < hi:
mid = lo + (hi - lo) // 2
if records[mid][0] < min_score:
lo = mid + 1
else:
hi = mid
return lo
records = [(50, 'Alice'), (72, 'Bob'), (72, 'Carol'), (88, 'Dave'), (95, 'Eve')]
idx = lower_bound_by_score(records, 72)
print(idx) # 1 (first record with score >= 72)
print(records[idx:]) # [(72,'Bob'),(72,'Carol'),(88,'Dave'),(95,'Eve')]Kesalahan Wawancara Umum pada Batas
Kesalahan yang paling umum adalah lupa melakukan validasi setelah memanggil bisect_left. Fungsi ini selalu mengembalikan indeks penyisipan yang valid, tetapi tidak menjamin elemen pada indeks tersebut sama dengan sasaran. Selalu periksa arr[result] == target sebelum menganggap sasaran telah ditemukan.
Kesalahan kedua adalah menggunakan bisect_right ketika Anda menginginkan kemunculan pertama — bisect_right mengembalikan posisi satu setelah kemunculan terakhir, sehingga pengurangan 1 menghasilkan posisi terakhir, bukan posisi pertama.
import bisect
arr = [1, 3, 5, 7]
target = 4
# bisect_left returns 2 (insertion point for 4 between 3 and 5)
idx = bisect.bisect_left(arr, target)
print(idx) # 2
# Validate: arr[2] is 5, not 4 => target absent
found = idx < len(arr) and arr[idx] == target
print('Found:', found) # FalseRingkasan: Kapan Menggunakan bisect_left dibandingkan bisect_right
Gunakan bisect_left ketika Anda memerlukan: kemunculan pertama sasaran, titik penyisipan yang menggeser salinan yang ada ke kanan, atau pemeriksaan apakah sasaran ada. Gunakan bisect_right ketika Anda memerlukan: posisi satu setelah kemunculan terakhir, titik penyisipan setelah semua salinan yang ada, atau jumlah elemen yang kurang dari atau sama dengan sasaran (nilainya sama dengan bisect_right(arr, target)).
Keduanya berjalan dalam O(log n) dan merupakan bagian dari pustaka standar Python, jadi Anda dapat langsung mengimpor dan menggunakannya kecuali pewawancara meminta Anda mengimplementasikannya dari awal.
Pemeriksaan Singkat
Uji pemahaman Anda tentang konsep Struktur Data & Algoritma — Persiapan Wawancara Pemrograman dari pelajaran ini.
Ringkasan Pelajaran
Dalam pelajaran ini Anda telah mempelajari: bisect_left menemukan elemen pertama >= sasaran, bisect_right menemukan elemen pertama > sasaran (satu posisi setelah kemunculan terakhir), dan selisih keduanya memberikan jumlah kemunculan dalam O(log n). Selanjutnya kita akan membahas pencarian biner pada ruang jawaban, ketika ruang pencarian berupa rentang kemungkinan jawaban, bukan indeks larik.
Pertanyaan yang Sering Diajukan
Apakah pelajaran “Batas Bawah dan Batas Atas” gratis?
Ya — teks lengkap “Batas Bawah dan Batas Atas” gratis dibaca di sini di web. Untuk praktiknya secara interaktif (editor kode bawaan dan tutor AI 24/7) dan buka sisa kursus DSA Interview Prep, upgrade ke CoddyKit PRO. Kursus DSA Interview Prep mencakup 4 pelajaran total.
Apa yang akan aku pelajari di “Batas Bawah dan Batas Atas”?
Implementasikan bisect_left dan bisect_right dari awal, lalu gunakan keduanya untuk menemukan posisi pertama dan terakhir suatu nilai target. Kamu berlatih DSA Interview Prep 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 DSA Interview Prep?
Tidak diperlukan pengalaman sebelumnya. DSA Interview Prep 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 “Batas Bawah dan Batas Atas” 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 DSA Interview Prep ini?
Ya. Setiap pelajaran DSA Interview Prep 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
- Pencarian Biner Klasik: Kiri, Kanan, Tengah
- Pencarian Biner pada Array Terputar dan Tak Terurut
- Batas Bawah dan Batas Atas
- Pencarian Biner pada Ruang Jawaban