İkili Arama

Doğrusal arama sırasız veri için eniyiydi. Varsayım değişirse sınır da değişir: dizi sıralıysa, bir karşılaştırma tek bir elemanı değil, kalan elemanların yarısını eler.

Bu ders o fikri işler. Fikir basittir; doğru yazmak değildir — ikili arama, yayımlanmış gerçekleştirimlerinde onlarca yıl hata barındırmış olmasıyla tanınır.

Aralık Değişmezi

Algoritma, hedefin bulunabileceği bir aralık tutar ve her turda aralığı yarıya indirir. Sınır hatalarından kaçınmanın yolu, aralığın anlamını en baştan yazmaktır.

Bu derste kapalı aralık kullanılır: [sol, sag] sınırlarının ikisi de aralığa dahildir.

def ikili_arama(dizi: list[int], hedef: int) -> int:
    """Sıralı dizide hedefin bir konumu; yoksa -1.

    Değişmez: hedef dizide varsa, [sol, sag] aralığındadır.
    Sonlanma: sag - sol her turda en az bir azalır.
    """
    sol, sag = 0, len(dizi) - 1
    while sol <= sag:
        orta = sol + (sag - sol) // 2
        if dizi[orta] == hedef:
            return orta
        if dizi[orta] < hedef:
            sol = orta + 1
        else:
            sag = orta - 1
    return -1


sirali = [1, 3, 4, 7, 9, 11, 15, 20]
print(ikili_arama(sirali, 9))      # 4
print(ikili_arama(sirali, 1))      # 0
print(ikili_arama(sirali, 20))     # 7
print(ikili_arama(sirali, 10))     # -1

Üç ayrıntı, gerçekleştirimin doğruluğunu taşır:

Döngü koşulu sol <= sag. Aralık kapalı olduğu için tek elemanlı aralık da geçerlidir; < yazılırsa son eleman hiç sınanmaz.

Sınırların orta ± 1 ile güncellenmesi. Sınanan eleman aralığın dışında bırakılır. sag = orta yazılırsa aralık küçülmeyebilir ve döngü sonsuza girer — sonlanma güvencesi tam olarak bu adımdan gelir.

Orta noktanın sol + (sag - sol) // 2 ile hesaplanması. (sol + sag) // 2 yazımı, sabit genişlikli tam sayı kullanan dillerde büyük dizilerde taşabilir. Bilgisayarlar Nasıl Çalışır kursundaki taşma davranışı burada somut bir hataya dönüşür.

Maliyet

Her tur aralığı yarılar ve sabit iş yapar:

$$T(n) = T(n/2) + O(1) \implies T(n) = O(\log n)$$

En kötü durumda karşılaştırma sayısı $\lfloor \log_2 n \rfloor + 1$’dir.

from collections.abc import Sequence


def sayimli_ikili_arama(dizi: Sequence[int], hedef: int) -> tuple[int, int]:
    sol, sag, sayac = 0, len(dizi) - 1, 0
    while sol <= sag:
        orta = sol + (sag - sol) // 2
        sayac += 1
        if dizi[orta] == hedef:
            return orta, sayac
        if dizi[orta] < hedef:
            sol = orta + 1
        else:
            sag = orta - 1
    return -1, sayac


for n in (1_000, 1_000_000, 1_000_000_000):
    # range dizinlenebilir olduğu için milyarlık dizi bellek ayrılmadan sınanır
    cift_sayilar = range(0, 2 * n, 2)
    print(n, sayimli_ikili_arama(cift_sayilar, n + 1)[1])   # tek sayı: dizide yok

# 1000 10
# 1000000 20
# 1000000000 30

Milyar elemanlı bir dizide otuz karşılaştırma yeterlidir. Doğrusal arama aynı işi bir milyar karşılaştırmayla yapar — Karmaşıklık Sınıflarını Okumak dersindeki ölçek büyütme tablosunun somut karşılığı budur.

Alan maliyeti $O(1)$’dir. Aynı algoritma özyinelemeli de yazılabilir, ancak o durumda $O(\log n)$ yığıt alanı kullanır.

Alt Sınır: Neden Daha Hızlısı Yok

Karşılaştırmaya dayalı arama, her adımda üç sonuçtan birini üretir: küçük, eşit, büyük. Algoritmanın davranışı bir karar ağacı olarak çizilirse, ağacın her yaprağı olası bir yanıttır ve $n$ elemanlı dizide en az $n$ farklı yanıt vardır.

Yüksekliği $h$ olan ikili bir ağacın en çok $2^h$ yaprağı olabilir. $2^h \geq n$ koşulundan $h \geq \log_2 n$ çıkar: karşılaştırmalı arama $\Omega(\log n)$’dir.

Aynı karar ağacı fikri, sıralamanın alt sınırında yeniden kullanılacak.

İlk ve Son Konum

Dizide yinelenen değerler varsa, yukarıdaki gerçekleştirim herhangi bir eşleşmeyi döndürür. Sıralamayla ilgili birçok işlem ise ilk eşleşmeyi ister.

Alt sınır (lower bound), hedeften küçük olmayan ilk elemanın konumudur. Eşleşme yoksa, hedefin sıralamayı bozmadan eklenebileceği yeri verir.

def alt_sinir(dizi: list[int], hedef: int) -> int:
    """dizi[i] >= hedef koşulunu sağlayan en küçük i (yoksa len(dizi)).

    Değişmez: yanıt [sol, sag] aralığındadır; aralık yarı açık tutulur.
    """
    sol, sag = 0, len(dizi)
    while sol < sag:
        orta = sol + (sag - sol) // 2
        if dizi[orta] < hedef:
            sol = orta + 1
        else:
            sag = orta
    return sol


tekrarli = [1, 3, 3, 3, 7, 9, 9]
print(alt_sinir(tekrarli, 3))      # 1   — ilk 3
print(alt_sinir(tekrarli, 9))      # 5   — ilk 9
print(alt_sinir(tekrarli, 4))      # 4   — eklenecek yer
print(alt_sinir(tekrarli, 10))     # 7   — dizinin sonu

Bu değişke yarı açık aralık kullanır: sag aralığa dahil değildir. Bu yüzden döngü koşulu sol < sag ve güncelleme sag = orta’dır. İki değişkeyi karıştırmak, ikili aramadaki hataların en yaygın kaynağıdır — aralığın hangi biçimde tutulduğu bir kez seçilir ve tüm satırlar ona göre yazılır.

Üst sınır, hedeften büyük ilk elemanı bulur; iki sonucun farkı, hedefin dizide kaç kez geçtiğini verir.

Sıralı Dizinin Ötesinde

İkili aramanın gerçek koşulu “dizi sıralı” değil, daha geneldir: tekdüze bir yüklem bulunmasıdır. Bir koşul, belirli bir noktaya kadar yanlış ve o noktadan sonra hep doğruysa, o nokta ikili aramayla bulunabilir.

def tam_karekok(n: int) -> int:
    """k*k <= n koşulunu sağlayan en büyük k."""
    sol, sag, yanit = 0, n, 0
    while sol <= sag:
        orta = sol + (sag - sol) // 2
        if orta * orta <= n:
            yanit = orta
            sol = orta + 1
        else:
            sag = orta - 1
    return yanit


print(tam_karekok(0), tam_karekok(15), tam_karekok(16), tam_karekok(10**18))
# 0 3 4 1000000000

Ortada bir dizi yoktur; aranan şey, orta * orta <= n yükleminin doğru kaldığı son değerdir. Yüklem tekdüze olduğu için yarıya bölme geçerlidir.

Bu genelleme yaygın bir tasarım aracıdır: “en küçük yeterli kapasite”, “en büyük geçerli eşik” biçimindeki problemler, doğrudan denenecek değer aralığı üzerinde ikili aramayla çözülür.

Ne Zaman Kullanılmaz

İkili arama üç varsayıma dayanır ve biri bozulduğunda tercih edilmez.

Sıralılık bedavaya gelmiyorsa. Tek bir arama için diziyi sıralamak $O(n \log n)$’dir; doğrusal arama $O(n)$. Sıralama ancak çok sorgulu kullanımda kendini öder.

Rastgele erişim yoksa. Bağlı listede orta elemana gitmek doğrusaldır ve logaritmik kazanç yok olur. Veri Yapıları kursundaki arama ağaçları, tam olarak bu boşluğu doldurur.

Veri sürekli değişiyorsa. Her eklemede sıralı diziyi güncellemek $O(n)$’dir; bu durumda dengeli ağaç veya karma tablosu daha uygundur.

Özet

• İkili arama sıralı veride aralığı yarılar; doğruluğu, aralığın anlamını sabit tutan bir değişmezle gerekçelendirilir.
• Kapalı ve yarı açık aralık değişkeleri farklı döngü koşulu ve güncelleme ister; ikisi karıştırılmamalıdır.
• Maliyet $T(n) = T(n/2) + O(1)$ bağıntısından $O(\log n)$ çıkar; alan $O(1)$’dir.
• Karar ağacı akıl yürütmesi, karşılaştırmalı aramanın $\Omega(\log n)$ olduğunu gösterir.
• Alt sınır değişkesi ilk eşleşmeyi veya ekleme konumunu verir.
• Yöntem, tekdüze bir yüklemin doğru olduğu ilk değeri arayan her probleme uygulanır.

Sonraki Adım

İkili aramanın koşulu sıralılıktı; öyleyse sıralamanın kendisi incelenmelidir. Sonraki ders üç temel sıralama algoritmasını — kabarcık, seçmeli ve eklemeli — karesel maliyetleri, kararlılıkları ve birbirlerinden ayrıldıkları noktalarla ele alacak.