İkili arama

Doğrusal arama veriyi baştan sona tek tek kontrol eder. Veri sıralıysa daha hızlı bir yol var: ikili arama (binary search). İkili arama, her adımda arama alanını (aranan değerin bulunabileceği bölgeyi) yaklaşık yarıya indirir.

Bu hafta ikili aramanın kodunu yazacağız. Yanında ön koşulunu ve en sık yapılan hataları da göreceğiz. Önce şu kuralı aklınızda tutun:

İkili arama yalnızca sıralı veride doğru sonuç verir.

1 Bu hafta neleri yapabilmelisiniz?

Bölümün sonunda:

  • İkili aramanın nasıl çalıştığını açıklayabilmeli,
  • Verinin neden sıralı olması gerektiğini gerekçelendirebilmeli,
  • low, high ve mid sınırlarını izleyebilmeli,
  • Döngüyle çalışan (iteratif) bir ikili arama fonksiyonu yazabilmeli,
  • Değerin bulunamadığı durumu ve sınır hatalarını ele alabilmeli,
  • Doğrusal ve ikili aramanın kaç karşılaştırma yaptığını kıyaslayabilmeli,
  • Python’ın bisect modülünü temel düzeyde kullanabilmelisiniz.

2 Temel fikir: arama alanını yarıya indir

Şu sıralı listeyi düşünelim:

[3, 7, 11, 15, 18, 24, 31, 42, 57]

42 değerini arıyoruz. Önce ortadaki değere bakarız:

[3, 7, 11, 15, 18, 24, 31, 42, 57]
                ↑
               18

42 > 18 olduğu için 42 solda olamaz, sol yarının tamamını eleriz. Sonra kalan sağ yarının ortasına bakarız. Arama alanı her adımda yarıya iner.

flowchart TD
    A["Tüm sıralı liste"] --> B{"hedef orta değerden küçük mü?"}
    B -- Evet --> C["sol yarıda devam et"]
    B -- Hayır --> D{"hedef orta değerden büyük mü?"}
    D -- Evet --> E["sağ yarıda devam et"]
    D -- Hayır --> F["bulundu"]

3 Neden sıralı olmak zorunda?

Şu liste sıralı değil:

[20, 5, 90, 12, 40]

40 değerini arıyoruz. Ortada 90 var. 40 daha küçük diye sağ tarafı atarsak 40’ı da atmış oluruz, çünkü 40 sağ taraftadır. Bir yarıya bakmadan eleyebilmemizin tek dayanağı sıralamadır: sıralı listede küçük değerler solda, büyükler sağda durur.

Important

Kodu yazmadan önce ön koşulu kontrol edin: veri, aradığınız ölçüte göre sıralı olmalıdır. Numaraya göre sıralanmış bir öğrenci listesinde adla ikili arama yapamazsınız.

4 Sınırlar: low, high, mid

İkili aramada üç indeks kullanırız:

  • low: şu anki arama alanının ilk indeksi,
  • high: şu anki arama alanının son indeksi,
  • mid: orta indeks.

Ortayı bulurken // (tam sayı bölmesi) kullanırız, çünkü indeks tam sayı olmalıdır.

5 İteratif ikili arama

Döngüde sınırlar şöyle güncellenir:

  • Hedef küçükse → high = mid - 1,
  • Hedef büyükse → low = mid + 1.

mid konumundaki elemana zaten baktık. Bu yüzden onu yeni arama alanının dışında bırakırız.

6 Adımları izleyelim

Her adımda low, high ve mid değerlerini yazdırınca low <= high koşulundaki ve mid ± 1 güncellemelerindeki hataları görmek kolaylaşır.

7 Alıştırma: ikili aramayı tamamla

Kontrol edilen mid konumunu yeni arama alanına tekrar dâhil etmeyin.

def binary_search(values, target):
    low = 0
    high = len(values) - 1

    while low <= high:
        mid = (low + high) // 2

        if values[mid] == target:
            return mid
        elif target < values[mid]:
            high = mid - 1
        else:
            low = mid + 1

    return -1

8 Doğrusal arama ile karşılaştırma

İki arama yönteminde kaç karşılaştırma yapıldığını sayalım:

1024 elemanlı sıralı bir listede son elemanı doğrusal arama 1024 kontrolde bulur. İkili arama ise yaklaşık 10 adımda sonuca ulaşır, çünkü arama alanı her adımda yarıya iner:

1024 → 512 → 256 → 128 → 64 → 32 → 16 → 8 → 4 → 2 → 1

Bu davranışı O(log n) ile gösteririz: eleman sayısı iki katına çıkınca adım sayısı yalnızca bir artar.

9 Ama sıralamanın da bir maliyeti var

İkili arama her durumda en iyi seçim değildir. Elinizde sıralı olmayan küçük bir veri varsa ve içinde yalnızca bir kez arama yapacaksanız önce sıralayıp sonra ikili arama yapmak gereksiz iş olabilir.

Veri zaten sıralıysa ya da aynı veride çok sayıda arama yapılacaksa ikili arama daha mantıklı olabilir.

Yapı ve algoritma seçerken tek bir aramaya bakmayın. Veriyle yapılacak bütün işleri düşünün: sıralamayı, eklemeyi, kaç kez arama yapılacağını.

10 Tekrar eden değerlerde ne olur?

Standart ikili arama eşleşen 4 değerlerinden herhangi birini bulabilir. Özellikle ilk 4 ya da son 4 gerekiyorsa algoritmayı değiştirmeniz gerekir. Bu yüzden arama fonksiyonunun sözleşmesi (hangi girdide ne döndüreceği) şu soruyu da cevaplamalıdır: herhangi bir eşleşme mi, ilk eşleşme mi?

11 Python’ın bisect modülü

Python’ın standart kütüphanesindeki bisect modülü, sıralı bir listeye yeni bir değerin nereye ekleneceğini ikili aramayla bulur:

30 listede olduğu için bisect_left onun indeksini (2) verir. 35 listede yok. Bu durumda bisect_left, sıralamayı bozmadan ekleneceği konumu (3) verir.

Warning

bisect konumu O(log n) adımda bulur. Ama bir Python listesinin ortasına eleman eklemek, arkadaki elemanları kaydırır. Bu da O(n) sürebilir. insort ikisini birlikte yaptığı için “ikili arama kullandım, bütün işlem O(log n)” demek her zaman doğru olmaz.

12 Kavram köşesi: ikili arama ağacı

İkili arama ağacı (binary search tree, BST) adı ikili aramaya benzer ve ikisi aynı sıralama fikrinden yararlanır. Yine de ikisini karıştırmayın. Bu derste ağaç yazmayacağız. Şimdilik şu ayrımı bilin:

  • İkili arama (binary search) → sıralı bir liste üzerinde çalışan bir arama algoritması,
  • İkili arama ağacı (BST) → düğümlerden oluşan ayrı bir veri yapısı.

13 Uç durumlar

İkili aramayı en az şu durumlarla sınayın:

14 Bölüm özeti

  • İkili arama, sıralı veride arama alanını her adımda yaklaşık yarıya indirir.
  • Ön koşulu, verinin sıralı olmasıdır.
  • low, high ve mid her adımda doğru güncellenmelidir.
  • İkili aramanın maliyeti O(log n)’dir.
  • Doğrusal aramanın maliyeti O(n)’dir, ama veri sıralı olmak zorunda değildir.
  • Hangisinin daha iyi olduğu, verinin zaten sıralı olup olmadığına ve kaç kez arama yapılacağına bağlıdır.
  • bisect sıralı listede konum bulmayı kolaylaştırır. Listeye eklemenin maliyetini ayrıca hesaba katın.

15 Kendinizi kontrol edin

  1. İkili aramanın temel ön koşulu nedir?
  2. Hedef orta değerden küçükse hangi sınır değişir?
  3. Standart uygulamaların çoğu neden high = mid yerine high = mid - 1 yazar?
  4. O(log n) büyümesini “yarıya indirme” fikriyle açıklayın.
  5. Sıralı olmayan bir veride yalnızca bir kez arama yapılacaksa doğrusal arama neden daha mantıklı olabilir?
Back to top