Linear/binary search ve arama kalıpları

Linear search hiçbir sıralılık istemez; her öğeyi sınar. Binary search sıralı veri veya false→true gibi monoton bir koşul ister. “Ortadan başla” tek başına yeterli değildir; hangi yarının neden elendiğini ispatla. [lo,hi) yarı açık aralık başlangıçta [0,n)'dir. lower_bound ilk a[i]≥x konumunu bulur; sonuç n ise uygun öğe yoktur.

Binary search yalnız bir değeri bulmak için değildir. Cevap uzayında minimum uygulanabilir kapasiteyi arayabilirsin: bir kapasite yeterliyse daha büyük kapasite de yeterli olmalıdır. Her feasibility kontrolünün maliyetini toplam hesaba ekle. Sırasız linked list üzerinde orta düğümü bulmak O(n) olduğundan, ikili daraltma array'deki erişim avantajını otomatik sağlamaz.

Two pointers sıralı çift toplamı, sliding window ise uygun pencere koşullarında çalışır. Negatif sayılar varsa toplamı aşınca soldan çıkarma stratejisi geçerli olmayabilir. Prefix sums aralık toplamını iki prefix farkına çevirir; prefix hash ile negatif içeren dizide hedef toplam alt dizi sayılabilir.

def lower_bound(a, x):
    lo, hi = 0, len(a)
    while lo < hi:
        mid = lo + (hi-lo)//2
        if a[mid] < x: lo = mid + 1
        else: hi = mid
    return lo
assert lower_bound([1,3,3,7], 3) == 1
assert lower_bound([], 9) == 0