İ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:

ikili 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,
iteratif 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.

#| edit: false
#| completion: false
values = [3, 7, 11, 15, 18, 24, 31, 42, 57]
low = 0
high = len(values) - 1
mid = (low + high) // 2

print("low:", low, values[low])
print("mid:", mid, values[mid])
print("high:", high, values[high])

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

5 İteratif ikili arama

#| edit: false
#| completion: false
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

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

print(binary_search(numbers, 42))
print(binary_search(numbers, 4))

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

#| edit: false
#| completion: false
def binary_search_trace(values, target):
    low = 0
    high = len(values) - 1
    step = 1

    while low <= high:
        mid = (low + high) // 2
        print(
            f"Adım {step}: low={low}, high={high}, mid={mid}, değer={values[mid]}"
        )

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

        step += 1

    return -1

values = [2, 5, 9, 13, 18, 21, 27, 34, 40, 51, 63]
print("Sonuç:", binary_search_trace(values, 34))

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

#| exercise: hafta08-binary
#| completion: false
#| persist: true
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 değerini güncelleyin
            pass
        else:
            # low değerini güncelleyin
            pass

    return -1

print(binary_search([4, 8, 15, 16, 23, 42], 23))

#| exercise: hafta08-binary
#| check: true
scope = {}
try:
    exec(user_code, scope)
    fn = scope.get("binary_search")
    correct = (
        callable(fn)
        and fn([4, 8, 15, 16, 23, 42], 23) == 4
        and fn([4, 8, 15, 16, 23, 42], 4) == 0
        and fn([4, 8, 15, 16, 23, 42], 42) == 5
        and fn([4, 8, 15, 16, 23, 42], 99) == -1
        and fn([], 1) == -1
    )
except Exception:
    correct = False

feedback = (
    {"correct": True, "message": "İkili arama sınırları doğru güncelleniyor."}
    if correct
    else {"correct": False, "message": "Hedef küçükse high = mid - 1; büyükse low = mid + 1 kullanın."}
)
feedback

Kontrol edilen mid konumunu yeni arama alanına tekrar dahil etmeyin.

Solution.

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:

#| edit: false
#| completion: false
def linear_checks(values, target):
    checks = 0
    for value in values:
        checks += 1
        if value == target:
            return checks
    return checks


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

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

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

    return checks

values = list(range(1, 1025))
target = 1024

print("Doğrusal:", linear_checks(values, target))
print("İkili:", binary_checks(values, target))

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:

veriyi sıralamak,
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?

#| edit: false
#| completion: false
values = [2, 4, 4, 4, 7, 9]
print(binary_search(values, 4))

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:

#| edit: false
#| completion: false
import bisect

values = [10, 20, 30, 40, 50]
position = bisect.bisect_left(values, 30)
print(position)

position = bisect.bisect_left(values, 35)
print(position)

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

#| edit: false
#| completion: false
import bisect

values = [10, 20, 30, 40]
bisect.insort(values, 25)
print(values)

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:

#| edit: false
#| completion: false
values = [5, 10, 15, 20]

assert binary_search(values, 5) == 0
assert binary_search(values, 20) == 3
assert binary_search(values, 15) == 2
assert binary_search(values, 99) == -1
assert binary_search([], 5) == -1

print("Tüm sınır kontrolleri geçti")

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

İkili aramanın temel ön koşulu nedir?
Hedef orta değerden küçükse hangi sınır değişir?
Neden high = mid yerine çoğu standart uygulamada high = mid - 1 kullanılır?
O(log n) sezgisini “yarıya indirme” fikriyle açıklayın.
Sıralı olmayan bir veri üzerinde yalnızca bir arama yapılacaksa neden doğrusal arama bazen daha mantıklı olabilir?

1 Bu hafta neleri yapabilmelisiniz?

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

3 Neden sıralı olmak zorunda?

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

5 İteratif ikili arama

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

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

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

9 Ama sıralamanın da bir maliyeti var

10 Tekrar eden değerlerde ne olur?

11 Python’ın bisect modülü

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

13 Sınır durumları

14 Bölüm özeti

15 Kendinizi kontrol edin

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

11 Python’ın `bisect` modülü