İkili Arama Algoritmasının Zaman Karmaşıklığı Nedir?

İkili arama algoritmasının zaman karmaşıklığı en kötü durumda O(log n), en iyi durumda O(1)'dir; burada n, listedeki eleman sayısıdır. Sıralı dizide arama alanı her adımda yaklaşık yarıya iner. Hedef ilk bakılan orta elemansa tek karşılaştırma yeterli olur. İkili aramada logaritmik süre, aranan alanın her adımda küçülmesinden kaynaklanır; bu sonuç için veri sıralı olmalıdır.

low, high ve middle: ikili arama adım adım nasıl çalışır?

Algoritma üç değişkenle yürür:

• low: aramanın sol sınırı, yani aranan alanın ilk indisi.
• high: aramanın sağ sınırı, yani aranan alanın son indisi.
• middle: middle = (low + high) // 2 ile bulunan orta indis.

Her turda orta eleman hedefle karşılaştırılır ve üç durumdan biri oluşur:

• Orta eleman hedefe eşitse eleman bulunmuştur ve middle döndürülür.
• Orta eleman hedeften küçükse hedef sağ yarıdadır; low = middle + 1 yapılır.
• Orta eleman hedeften büyükse hedef sol yarıdadır; high = middle - 1 yapılır.

Buradaki + 1 ve - 1 önemlidir. Orta eleman zaten kontrol edildiği için aralığın dışına çıkarılır. Böylece aralık her turda gerçekten daralır ve döngü sonsuza gitmez.

Başarısız aramanın bitiş koşulu da buradan çıkar. low, high'ı geçtiğinde (low > high) bakılacak hiçbir indis kalmamıştır. Bu durumda fonksiyon -1 döndürür. Aşağıdaki Python fonksiyonu bu kuralların tamamını içerir:

def ikili_arama(liste, hedef):
    low = 0
    high = len(liste) - 1

    while low <= high:
        middle = (low + high) // 2
        if liste[middle] == hedef:
            return middle
        elif liste[middle] < hedef:
            low = middle + 1
        else:
            high = middle - 1

    return -1


sayilar = [2, 5, 8, 12, 16, 23, 38, 45, 56, 72, 91]
print(ikili_arama(sayilar, 45))
print(ikili_arama(sayilar, 40))

Beklenen çıktı:

7
-1

45 listenin 7 numaralı indisinde durduğu için ilk çağrı 7 döndürür. 40 listede olmadığı için ikinci çağrı -1 verir. Döngü koşulunun low <= high olduğuna dikkat et: < yazarsan son kalan tek elemanlı aralık hiç kontrol edilmez ve aranan değer o elemansa yanlışlıkla -1 alırsın.

Sıralı bir listede bir sayıyı adım adım izleyelim

Aynı listeyi indisleriyle düşün: 0 için 2, 1 için 5, 2 için 8, 3 için 12, 4 için 16, 5 için 23, 6 için 38, 7 için 45, 8 için 56, 9 için 72, 10 için 91. Önce hedef 45 olsun.

1. Adım 1: low=0, high=10, middle=5, değer 23. 23 < 45 olduğu için hedef sağdadır; low=6 olur.
2. Adım 2: low=6, high=10, middle=8, değer 56. 56 > 45 olduğu için hedef soldadır; high=7 olur.
3. Adım 3: low=6, high=7, middle=6, değer 38. 38 < 45 olduğu için low=7 olur.
4. Adım 4: low=7, high=7, middle=7, değer 45. Eşleşme var, eleman bulundu; sonuç 7.

Başlangıçta 11 elemanlık alan vardı. Dört karşılaştırma sonunda aranan değere ulaştık ve listenin büyük kısmına hiç bakmadık.

Şimdi listede olmayan 40'ı arayalım. İlk üç adım yukarıdakine çok benzer ilerler:

1. Adım 1: middle=5, değer 23. 23 < 40 olduğu için low=6.
2. Adım 2: middle=8, değer 56. 56 > 40 olduğu için high=7.
3. Adım 3: middle=6, değer 38. 38 < 40 olduğu için low=7.
4. Adım 4: low=7, high=7, middle=7, değer 45. 45 > 40 olduğu için high=6 olur.

Bu noktada low=7, high=6 olduğundan low <= high koşulu sağlanmaz ve döngü biter. Aralık boşaldı, yani 40 listede yok; fonksiyon -1 döndürür.

Sınavda iz sürme sorusu gelirse her turda low, high ve middle değerlerini alt alta yazman yeterlidir. Hatanın çoğu, high'ı güncellerken middle - 1 yerine yanlışlıkla middle yazmakta ya da low ile high değerlerini karıştırmakta ortaya çıkar. Tabloyla göreceğimiz kalan eleman sayısı, bu daralmanın neden O(log n) verdiğini gösterecek.

O(log n) sonucu nereden gelir?

İkili aramada logaritmik süre, aranan alanın her adımda küçülmesinden kaynaklanır; bu sonuç için veri sıralı olmalıdır. Her karşılaştırmada orta eleman kontrol edilir ve geriye kalan alanın yarısı ya da yarısına yakını elenir. Bunu n = 16 elemanlı sıralı bir liste üzerinde, en kötü durumu varsayarak görelim:

İlk satırdaki 8 değerine dikkat et: 16 elemandan birini kontrol ettiğimiz için orta eleman da elenir. Geriye 15 eleman kalır ve büyük olan taraf en fazla 8 elemandır. Bu yüzden her turda kalan sayı tam olarak değil, yaklaşık yarıya iner.

Tablodan log2(n) + 1 sonucuna

Tabloyu okuyunca mantık sadeleşir. Alan 1 elemana inene kadar sürekli yarıya bölünür ve bu bölme sayısı log2(n) kadardır. n = 16 için log2(16) = 4, tabloda da 4. karşılaştırmadan sonra tek eleman kalıyor. Kalan o son elemanı kontrol etmek için bir karşılaştırma daha gerekir. Bu yüzden en kötü durumda en fazla yaklaşık log2(n) + 1 karşılaştırma yapılır; n = 16 için bu sayı 5'tir.

Büyük O gösteriminde sabit terimler ve logaritmanın tabanı önemsizleştirilir. Buradaki "+ 1" bir sabittir; taban değişimi de yalnızca sabit bir çarpan getirir. Sonuç olarak en kötü durum O(log n) yazılır.

En iyi durum ise hedefin ilk middle değerinde çıkmasıdır. O zaman tek karşılaştırma yeter ve süre O(1) olur.

Doğrusal aramayla fark kavramsaldır: doğrusal arama her adımda yalnızca tek elemanı eler, ikili arama ise kalan alanın yaklaşık yarısını. Alan bu hızla küçüldüğü için adım sayısı n ile birlikte doğrusal değil, logaritmik büyür.

Liste sıralı değilse ikili arama neden yanlış sonuç verir?

Çünkü orta elemanla yapılan karşılaştırma, yalnızca sıralı veride "küçükler hep solda, büyükler hep sağda" bilgisini verir. Sırasız veride bu bilgi yoktur ve bir yarım güvenle elenemez. Aşağıdaki karşı örnek bunu gösteriyor.

Sıralı olmayan [9, 3, 14, 1, 20, 7, 11] listesinde hedef 3 olsun. 3, indis 1'de, yani listede mevcut.

1. Başlangıçta low = 0, high = 6 olur; middle = 3 çıkar ve o indisteki değer 1'dir.
2. 3 > 1 olduğu için algoritma "hedef sağda olmalı" kabul eder ve low = 4 yapar. Oysa 3 sol yarıda kalmıştır.
3. Kalan alan 4-6 indisleridir. middle = 5, değer 7; 3 < 7 olduğundan high = 4 olur.
4. middle = 4, değer 20; 3 < 20 olduğundan high = 3 olur ve low > high durumu oluşur.

Algoritma -1 döndürür: eleman listede olduğu halde bulunamaz. Hata kodda değil, varsayımdadır. İkinci adımda 1 değerine bakıp sağa gitmek, ancak 1'den küçük her şeyin solda olduğu bir düzende anlamlıdır.

İki çözüm yolu var. Birincisi listeyi önce sıralamaktır. Sıralamanın da kendi maliyeti vardır; bu yüzden ancak aynı veride çok sayıda arama yapılacaksa mantıklıdır. İkincisi sırasız veride elemanlara tek tek bakmaktır, yani doğrusal arama.

Böyle koşulları ve karşı örnekleri kendi başına çalıştırmak istersen dilden bağımsız hazırlanmış ücretsiz Algoritmik Düşünme Testi ile bu düşünme biçimini deneyebilirsin.

Sınavda ve derste kendini kontrol etmek için kısa liste

İkili arama kodunu yazdıktan ya da sınav kâğıdında çözdükten sonra şu noktalara göz atabilirsin:

• Veri sıralı mı? Sıralama yoksa "aranan alanın yarısını ele" adımı geçerli olmaz.
• Döngü koşulu low <= high mı? Tek eleman kaldığında da kontrol yapılmalıdır.
• Daraltırken middle + 1 ve middle - 1 kullanılıyor mu? middle değerinin kendisini tekrar aralığa katarsan döngü sonsuza gidebilir.
• Bulunamadı durumu ele alınıyor mu? Döngü bittiğinde genellikle -1 döndürülür.
• n = 16 gibi küçük bir listede adım sayısını elle sayabiliyor musun? Kalan eleman sayısı 16, 8, 4, 2, 1 diye azaldığı için sayım kısa sürer.

Kendi örnek listeni seçip hedefi sırayla başa, sona, ortaya ve listede olmayan bir değere koyarak izleme yapmayı deneyebilirsin. Her denemede low, high ve middle değerlerini bir tabloya yazmak, hatanın hangi adımda başladığını görmeni kolaylaştırır.

Bu kontrollerin çoğu, algoritmayı koddan önce kâğıt üzerinde düşünerek kurduğunda kendiliğinden ortaya çıkar. Önce aralığın nasıl daralacağını ve ne zaman duracağını yazılı olarak ifade etmek, kodu sonradan düzeltme ihtiyacını azaltabilir. Python ile bu tür algoritma pratiği yapmak isteyen lise ve üniversite öğrencileri, birebir Python Özel Ders programını inceleyebilir.

Bir sonraki ikili arama sorusunda önce hedefi ve aralığı yaz, sonra kodu yaz.