Alt Sınır ve Üst Sınır
bisect_left ve bisect_right işlevlerini sıfırdan uygulayın, ardından bunları hedef değerin ilk ve son konumlarını bulmak için kullanın.
Alt Sınır ve Üst Sınır, CoddyKit'te ücretsiz bir Coding Interview Prep dersidir. Bu, 4 dersinin 3. dersidir. Aşağıdan dersin tamamını ücretsiz okuyabilir, sonra tarayıcıda yerleşik kod editörü ve 7/24 yapay zeka koçu ile uygulamalı olarak pratik yapabilirsin. Bu, Coding Interview Prep öğrenme yolunun bir parçasıdır ve ilerlemeniz web ve CoddyKit uygulaması arasında senkronize olur. Coding Interview Prep kursu toplamda 4 dersten oluşur.
Alt ve Üst Sınırlar Nedir?
Sıralı bir dizide hedef değerin alt sınırı, hedeften büyük veya hedefe eşit olan ilk elemanın dizinidir (genellikle bisect_left olarak adlandırılır). Üst sınır ise hedeften kesinlikle büyük olan ilk elemanın dizinidir (bisect_right). Bu ikisi birlikte hedefin her oluşumunu sınırlar ve O(log n) aralık sorgularını mümkün kılar.
Bu iki işlem birçok mülakat probleminin temelini oluşturur: tekrar sayısını bulma, aralık bulma, ekleme konumu ve daha fazlası.
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)Alt Sınırı (bisect_left) Uygulama
bisect_left(arr, x), arr[i] >= x koşulunu sağlayan en soldaki i dizinini döndürür; tüm elemanlar daha küçükse len(arr) döndürür. Uygulama, üst sınırı dışlayan bir sınır kullanır: hi = len(arr), döngü koşulu lo < hi ve arr[mid] >= x olduğunda hi = mid güncellemesi. Bu, sonucun geçerli en soldaki konuma yakınsamasını sağlar.
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)) # 4Üst Sınırı (bisect_right) Uygulama
bisect_right(arr, x), arr[i] > x koşulunu sağlayan en soldaki i dizinini döndürür. bisect_left ile arasında yalnızca bir satır farklıdır: koşul arr[mid] < x yerine arr[mid] <= x olur. arr[mid] <= x olduğunda sonuç mid'in kesinlikle sağındadır; bu nedenle lo = mid + 1 yaparız. Aksi hâlde aralığı sağdan daraltırız.
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)) # 5Her İki Sınırla Tekrarları Sayma
Sıralı bir dizide bir hedefin tekrar sayısını O(log n) içinde bulmak için her iki sınırı uygulayın: tekrar sayısı = bisect_right(arr, target) - bisect_left(arr, target). Sayı 0 ise hedef mevcut değildir. Bu yöntem doğrusal taramadan önemli ölçüde daha hızlıdır ve sıralı verilerdeki sıklık sorguları için standart yaklaşımdır.
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)) # 1Hedefin İlk ve Son Konumunu Bulma
LeetCode 34, “Sıralı Dizide Bir Elemanın İlk ve Son Konumunu Bulma”, sizden O(log n) içinde [first_idx, last_idx] değerlerini döndürmenizi ister. İlk konum bisect_left(arr, target) değeridir; ancak yalnızca arr[result] == target ise. Son konum ise bisect_right(arr, target) - 1 değeridir. Kontrollerden biri başarısız olursa [-1, -1] döndürün.
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]Ekleme Konumu (LeetCode 35)
LeetCode 35, “Arama Ekleme Konumu”, şu soruyu sorar: diziyi sıralı tutmak için hedef nereye eklenmelidir? Bu, tam olarak bisect_left(arr, target) değeridir. Hedef mevcutsa bisect_left hedefin dizinini döndürür. Mevcut değilse bisect_left, hedefin ekleneceği dizini döndürür. Özel durum işlemesi gerekmez — aynı işlev her iki durumu da ele alır.
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)bisect_left ile bisect_right Arasındaki Fark
Yinelenen değerler yoksa bisect_left ve bisect_right aynı dizini döndürür. Fark yalnızca hedef birden çok kez göründüğünde önem kazanır. bisect_left ilk örneği gösterir; bisect_right ise son örneğin bir sonrasını gösterir. Mevcut örneklerden önce mi (sol) yoksa sonra mı (sağ) ekleme yapmak istediğinize göre doğru olanı seçin.
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)) # 4Sıralı Frekans Sorgularına Sınırları Uygulama
Sıralı bir dizide çok sayıda aralık-frekans sorgusunu verimli biçimde yanıtlamanız gerektiğinde, sıralı diziyi bir kez oluşturun ve her sorgu için sınır bulma işlemlerini kullanın. Her sorgu, O(n) yerine O(log n) içinde '[lo, hi] aralığında kaç eleman bulunuyor?' sorusunu yanıtlar. Bu örüntü, sıralama sonrasında belirli bir değer aralığındaki elemanları saymaya yönelik problemlerde görülür.
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)Özel Anahtarla İkili Arama
Bazen arama anahtarı, saklanan değerin kendisi değil, türetilmiş bir özelliktir. Python'ın bisect modülü doğrudan bir anahtar işlevini desteklemez; ancak döngü içinde anahtarı uygulayarak ikili aramayı elle gerçekleştirebilirsiniz. Bu örüntü, bir nesne listesini nesnelerin özelliklerinden birine göre ararken kullanılır.
# 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')]Sınırlarla İlgili Yaygın Mülakat Hataları
En yaygın hata, bisect_left çağrısından sonra doğrulama yapmayı unutmaktır. İşlev her zaman geçerli bir ekleme dizini döndürür; ancak o dizindeki elemanın hedefe eşit olduğunu garanti etmez. Hedefin bulunduğunu varsaymadan önce her zaman arr[result] == target kontrolünü yapın.
İkinci bir hata, ilk oluşumu istediğiniz hâlde bisect_right kullanmaktır — bisect_right son oluşumun bir sonrasını döndürür; dolayısıyla 1 çıkarmak ilkini değil, sonuncuyu verir.
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) # FalseÖzet: bisect_left ile bisect_right Ne Zaman Kullanılır
Şunlara ihtiyacınız olduğunda bisect_left kullanın: hedefin ilk oluşumu, mevcut örnekleri sağa kaydıran ekleme noktası veya hedefin mevcut olup olmadığını kontrol etmek. Şunlara ihtiyacınız olduğunda bisect_right kullanın: son oluşumun bir sonrası, tüm mevcut örneklerden sonraki ekleme noktası veya hedefe <= olan elemanların sayısı (bu, bisect_right(arr, target) değerine eşittir).
Her ikisi de O(log n) içinde çalışır ve Python standart kitaplığının parçasıdır. Bu nedenle, mülakatı yapan kişi sizden sıfırdan uygulamanızı istemediği sürece bunları doğrudan içe aktarıp kullanabilirsiniz.
Hızlı Kontrol
Bu dersteki Veri Yapıları ve Algoritmalar — Kodlama Mülakatına Hazırlık kavramlarını anlayıp anlamadığınızı test edin.
Ders Özeti
Bu derste şunları öğrendiniz: bisect_left, >= hedefini sağlayan ilk elemanı bulur, bisect_right, > hedefini sağlayan ilk elemanı bulur (son oluşumun bir sonrasını) ve ikisinin farkı, oluşumların sayısını O(log n) içinde verir. Sırada, arama alanının bir dizi dizini değil, olası yanıtlar aralığı olduğu yanıt uzayında ikili aramayı inceleyeceğiz.
Sıkça Sorulan Sorular
“Alt Sınır ve Üst Sınır” dersi ücretsiz mi?
Evet — “Alt Sınır ve Üst Sınır” dersin tüm metni burada web'de ücretsiz olarak okunabilir. Etkileşimli olarak pratik yapmak (yerleşik kod editörü ve 7/24 yapay zeka koçu) ve Coding Interview Prep kursunun geri kalanını açmak için CoddyKit PRO'ya yükselt. Coding Interview Prep kursu toplamda 4 dersten oluşur.
“Alt Sınır ve Üst Sınır” dersinde ne öğreneceğim?
bisect_left ve bisect_right işlevlerini sıfırdan uygulayın, ardından bunları hedef değerin ilk ve son konumlarını bulmak için kullanın. Coding Interview Prep ile uygulamalı kodu tarayıcıda doğrudan çalıştırarak pratik yaparsın ve 7/24 yapay zeka koçu dersi çalışırken sorularını yanıtlar.
Coding Interview Prep öğrenmeye başlamak için deneyim gerekli mi?
Önceden deneyim gerekmez. CoddyKit'te Coding Interview Prep, başlangıçtan ileri seviyeye kadar yapılandırıldığı için buradan başlayabilir veya başından başlayıp kendi hızında ilerleme yapabilirsin. Bu, 4 dersinin 3. dersidir.
“Alt Sınır ve Üst Sınır” dersi ne kadar sürer?
Çoğu CoddyKit dersi yaklaşık 5–10 dakika sürer. Her biri kısa ve etkileşimli olduğu için sabit ilerleme yaparsın ve web ile uygulama arasında tam olarak bıraktığın yerden devam edebilirsin.
Bu Coding Interview Prep dersinde kod yazıp çalıştırabilir miyim?
Evet. Her Coding Interview Prep dersi yerleşik bir kod editörü içerir, bu sayede tarayıcıda gerçek kod yazıp çalıştırabilir ve anlık yapay zeka geri bildirimi alırsın — yerel kurulum gerekli değildir.
Bu kursun tüm dersleri
- Klasik İkili Arama: Sol, Sağ, Orta
- Döndürülmüş ve Sıralanmamış Dizilerde İkili Arama
- Alt Sınır ve Üst Sınır
- Yanıt Uzayında İkili Arama