İkili arama

Doğrusal arama, veriyi baştan sona kontrol eder. Ancak veri sıralıysa, arama alanını her adımda yaklaşık yarıya indiren daha güçlü bir yöntem kullanabiliriz: ikili arama (binary search).

Bu hafta ikili aramanın yalnızca kodunu değil, en önemli ön koşulunu ve hata kaynaklarını inceleyeceğiz. Temel ilke şudur:

İkili arama yalnızca uygun biçimde sıralanmış veri üzerinde anlamlıdır.

1 Bu hafta neleri yapabilmelisiniz?

Bölümün sonunda:

  • İkili aramanın çalışma mantığını açıklayabilmeli,
  • Sıralı veri ön koşulunu gerekçelendirebilmeli,
  • low, high ve mid sınırlarını izleyebilmeli,
  • İteratif ikili arama fonksiyonu yazabilmeli,
  • Bulunamama ve sınır hatalarını yönetebilmeli,
  • Doğrusal ve ikili aramayı karşılaştırma sayısı bakımından karşılaştırabilmeli,
  • 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 sol yarının tamamını eleyebiliriz. Sonra kalan sağ yarının ortasına bakarız. Her adımda arama alanı küçülür.

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]

Ortadaki 90 değerine bakıp aranan 40 daha küçük diye sağ tarafı atarsak, 40 gerçekten sağ tarafta olduğu hâlde yanlış karar veririz. İkili aramanın yarıyı güvenle elemesi ancak sıralama ilişkisi sayesinde mümkündür.

Important

İkili aramanın en kritik bilgisi kod değil, ön koşuldur: veri arama ölçütüne göre sıralı olmalıdır.

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

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

  • low: geçerli arama alanının ilk indeksi,
  • high: geçerli arama alanının son indeksi,
  • mid: orta indeks.

// tamsayı bölmesi kullanılır; indeks tamsayı olmak zorundadır.

5 İteratif ikili arama

Dikkat edilmesi gereken güncellemeler:

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

mid elemanını zaten kontrol ettiğimiz için onu tekrar arama alanında bırakmayız.

6 Adımları görünür kılalım

Kodun ara durumlarını izlemek, özellikle low <= high ve mid ± 1 hatalarını anlamayı kolaylaştırır.

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

Kontrol edilen mid konumunu yeni arama alanına tekrar dahil 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 bulabilirken ikili arama yaklaşık 10 adım civarında tamamlanır. Çünkü:

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

Bu davranış O(log n) sezgisiyle ifade edilir.

9 Ama sıralamanın da bir maliyeti var

İkili arama her durumda otomatik olarak en iyi seçim değildir. Elinizde sıralı olmayan küçük bir veri varsa ve yalnızca bir kez arama yapacaksanız:

  1. Veriyi sıralamak,
  2. Sonra ikili arama yapmak

gereksiz iş olabilir.

Buna karşılık veri zaten sıralıysa veya aynı veri üzerinde çok sayıda arama yapılacaksa ikili arama daha anlamlı olabilir.

Veri yapısı ve algoritma kararında yalnızca tek bir işlemi değil, bütün iş akışını düşünün.

10 Tekrar eden değerlerde ne olur?

Standart ikili arama, eşleşen 4 değerlerinden herhangi birini bulabilir. Eğer “ilk 4” veya “son 4” özellikle isteniyorsa algoritma değiştirilmelidir. Bu ayrıntı, arama fonksiyonunun sözleşmesinin neden önemli olduğunu gösterir.

11 Python’ın bisect modülü

Python standart kütüphanesindeki bisect, sıralı listelerde ekleme konumu bulmak için ikili arama yaklaşımını kullanır:

bisect_left, değer listede yoksa sıralamayı koruyacak ekleme konumunu verir.

Warning

bisect arama konumunu O(log n) sezgisiyle bulsa da, bir Python listesinin ortasına gerçek ekleme yapmak elemanları kaydırdığı için O(n) maliyet taşıyabilir. “İkili arama kullandım, bütün işlem O(log n)” sonucu her zaman doğru değildir.

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

Binary Search Tree (BST) terimi, ikili aramayla ilişkili bir sıralama fikri taşır; ancak Python listesi üzerinde yaptığımız ikili aramayla aynı veri yapısı değildir. Bu derste ağaç uygulaması yapmayacağız. Şimdilik şu ayrımı bilin:

  • Binary search → sıralı dizisel veri üzerinde arama algoritması,
  • Binary search tree → düğümlerden oluşan ayrı bir veri yapısı.

13 Sınır 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 sıralı veridir.
  • low, high, mid sınırlarının doğru güncellenmesi kritik önemdedir.
  • İkili arama O(log n) sezgisine sahiptir.
  • Doğrusal arama O(n) sezgisine sahiptir ve sıralama gerektirmez.
  • En iyi yöntem, verinin mevcut düzenine ve kaç kez arama yapılacağına bağlıdır.
  • bisect sıralı listelerde konum bulmak için kullanışlıdır; ancak listeye ekleme maliyeti ayrıca düşünülmelidir.

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. Neden high = mid yerine çoğu standart uygulamada high = mid - 1 kullanılır?
  4. O(log n) sezgisini “yarıya indirme” fikriyle açıklayın.
  5. Sıralı olmayan bir veri üzerinde yalnızca bir arama yapılacaksa neden doğrusal arama bazen daha mantıklı olabilir?
Back to top