Sıralı bir listede belirli bir sayının bulunup bulunmadığını öğrenmek, arama problemlerinin yalnızca başlangıcıdır. Aynı sayı birkaç kez geçiyorsa ilk konumu nasıl bulunur? Belirli iki değer arasında kaç kayıt vardır? Bu yazıda ikili aramayı, tek bir eşleşme arayan işlem yerine iki bölge arasındaki sınırı bulan bir algoritma olarak kuracağız. Python’ın bisect belgeleri de işlemleri doğrudan eşitlik aramak yerine ekleme konumu bulmak üzerinden tanımlar.
1. Önce sonucun anlamını belirleyin
Örnek listemiz [2, 4, 4, 4, 7, 9] olsun. Hedefimiz 4 olduğunda herhangi bir eşleşmenin konumunu döndürmek yeterli değildir: 1, 2 ve 3 indisleri aynı değeri gösterir. Bunun yerine şu soruyu soralım: Hedeften küçük olmayan ilk eleman hangi konumdadır? Bu örnekte yanıt 1 olur. Hedef 5 olduğunda ise yanıt 4 olur; çünkü o konumda bulunan 7, yeni değerin önüne geçemeyeceği ilk elemandır.
Bu konuma sol sınır diyeceğiz. Solundaki bütün değerler hedeften küçüktür; sağındaki bütün değerler hedefe eşit veya büyüktür. Hedef bütün elemanlardan büyükse sonuç listenin uzunluğudur. Dolayısıyla dönen sayı her zaman okunabilecek bir elemanın indisi değildir. Bu sözleşme, resmi bisect_left açıklamasıyla örtüşür.
2. Arama aralığını yarı açık tutun
Aşağıdaki özgün öğretici uygulamada aday konumları [lo, hi) aralığıyla izleyeceğiz. Sol uç dahil, sağ uç hariçtir. Başlangıçta lo = 0 ve hi = len(a) seçilir. Böylece boş liste için de ayrı bir dal yazmak gerekmez. Döngü boyunca henüz karar vermediğimiz elemanlar bu aralıktadır.
def sol_sinir(a, hedef):
lo, hi = 0, len(a)
while lo < hi:
mid = lo + (hi - lo) // 2
if a[mid] < hedef:
lo = mid + 1
else:
hi = mid
return lo
sayilar = [2, 4, 4, 4, 7, 9]
assert sol_sinir(sayilar, 4) == 1
assert sol_sinir(sayilar, 5) == 4
assert sol_sinir(sayilar, 10) == 6
assert sol_sinir([], 4) == 0Ortadaki eleman hedeften küçükse onu ve solundaki bütün elemanları eleriz. Çünkü sıralı listede bunların hiçbiri aranan sınır olamaz. Bu yüzden sol ucu mid + 1 yaparız. Diğer durumda ortadaki eleman hâlâ cevap olabilir; sağ ucu mid yaparak onu sınır adayı olarak koruruz. Aynı karar yapısı CPython’ın bisect_left uygulamasında da görülebilir.
3. Bir örneği elle yürütün
Altı elemanlı örneğimizde hedef yine 4 olsun. Başlangıç aralığı [0, 6) olur. Aşağıdaki tablo, kodun değerleri nasıl daralttığını gösteren elle çıkarılmış bir izdir; performans ölçümü değildir.
| lo | hi | mid | Ortadaki değer | Karar |
|---|---|---|---|---|
| 0 | 6 | 3 | 4 | hi = 3 |
| 0 | 3 | 1 | 4 | hi = 1 |
| 0 | 1 | 0 | 2 | lo = 1 |
Son durumda iki uç da 1 olur. Artık incelenecek eleman kalmamıştır ve sınır belirlenmiştir. Dikkat edilmesi gereken nokta, eşitlik görüldüğünde hemen dönmememizdir. İlk 4 değerini bulmak için solda başka bir eşleşme olup olmadığını araştırmaya devam ederiz.
4. Neden doğru sonuç verir?
Doğruluk gerekçesini üç parçaya ayırabiliriz. Başlangıçta sol tarafta elenmiş eleman yoktur; sağ tarafta da henüz bir kısıtlama yapılmamıştır. Her adımda, elenen sol bölümde yalnızca hedeften küçük değerler, sağ bölümde ise yalnızca hedefe eşit veya büyük değerler bulunduğunu koruruz. Bu, döngünün değişmezidir.
Ayrıca her turda aralık kesin olarak küçülür: ya sol uç ortanın ilerisine gider ya da sağ uç ortaya çekilir. Sonunda uçlar birleşir. Birleşme noktasının solundaki hiçbir eleman cevaba uygun değildir; sağındaki bütün elemanlar koşulu sağlar. Bu nedenle birleşme noktası aradığımız ilk konumdur. Bu gerekçe, yukarıdaki kod ve sıralılık varsayımı üzerinden yapılan çıkarımdır.
5. Eşleşme kontrolünden aralık sayımına geçin
Sol sınırın bulunması, hedefin listede bulunduğu anlamına gelmez. Örneğin 5 için dönen konumda 7 vardır. Kesin eşleşme gerekiyorsa önce sonucun liste uzunluğundan küçük olduğunu, ardından o konumdaki değerin hedefe eşit olduğunu kontrol edin. Python belgelerindeki sıralı listede arama örnekleri de bu iki kontrolü birlikte kullanır.
Şimdi sağ sınırı tanımlayalım: hedeften kesin olarak büyük ilk elemanın konumu. Sol sınır eşitlerin önünde, sağ sınır eşitlerin arkasında kalır. Bu iki konumun farkı, tekrar sayısını verir. Aynı fikirle kapalı bir değer aralığındaki elemanları da sayabiliriz. Sınırların standart kütüphanedeki karşılıkları bisect_left ve bisect_right işlevleridir; davranışları resmi belgede tanımlanır.
from bisect import bisect_left, bisect_right
def aralik_sayisi(a, alt, ust):
if alt > ust:
return 0
return bisect_right(a, ust) - bisect_left(a, alt)
sayilar = [2, 4, 4, 4, 7, 9]
assert bisect_right(sayilar, 4) - bisect_left(sayilar, 4) == 3
assert aralik_sayisi(sayilar, 4, 7) == 4
assert aralik_sayisi(sayilar, 5, 6) == 0
assert aralik_sayisi(sayilar, 9, 2) == 06. Maliyeti ve kullanım sınırını ayırın
Bu kodda her tur aday aralığını yaklaşık yarıya indirir. İndisle erişimin ve karşılaştırmanın sabit zaman aldığı varsayımıyla sol sınır araması O(log n) zaman, yalnızca birkaç indis tuttuğu için O(1) ek alan kullanır. İki sınır arayan sayım da aynı asimptotik maliyettedir. Bunlar koddan türetilen sınırlardır; CPython kaynağındaki daralan aralıklı döngüler aynı analizi izlemeyi mümkün kılar.
Ancak konumu bulmakla listeye eleman eklemek aynı işlem değildir. Resmi performans notları, listeye sıralı eklemede O(n) ekleme maliyetinin logaritmik aramaya baskın geldiğini belirtir. Bu yüzden çok sayıda ekleme yapılan bir iş yükünü yalnızca arama karmaşıklığıyla değerlendirmeyin.
Temel kullanım sınırı sıralılıktır. Örneğin [4, 2, 7] girdisinde yukarıdaki eleme gerekçesi geçersizdir. Arama sırasında listeyi değiştirmeyin; karşılaştırmaların tutarlı olmasını sağlayın. Alıştırma olarak tek elemanlı, tüm değerleri eşit ve hedefi hiç içermeyen listeler için beklenen sınırları önce kâğıt üzerinde çıkarın. Amaç döngüyü ezberlemek değil, her adımda hangi bölgenin neden elendiğini açıklayabilmektir.
Kaynaklar
