İkili Arama

#Nasıl çalışır?

İkili arama (binary search), sıralı bir dizide aranan değeri her adımda arama aralığını ikiye bölerek bulur. Sözlükte kelime ararken ortalardan bir sayfa açıp aradığın kelimenin önde mi arkada mı kaldığına bakmak gibidir.

Aralığın ortasındaki eleman aranan değerle karşılaştırılır. Eşitse bulunmuştur. Ortadaki daha küçükse aranan değer sağ yarıdadır; daha büyükse sol yarıdadır. Diğer yarı tamamen elenir.

Her adımda aralık yarıya indiği için 1 milyon elemanlı bir dizide bile en fazla 20 karşılaştırma yeter. Tek şart verinin sıralı olmasıdır.

#Canlı animasyon

lo = 0; hi = n - 1
while lo <= hi
  mid = (lo + hi) / 2
  if a[mid] == target: return mid
  if a[mid] < target: lo = mid + 1
  else: hi = mid - 1
return -1

#Adım adım

1. 01lo = 0 ve hi = n - 1 ile tüm diziyi arama aralığı olarak al.
2. 02Ortadaki elemanı bul: mid = (lo + hi) / 2.
3. 03a[mid] aranan değere eşitse mid'i döndür.
4. 04a[mid] aranan değerden küçükse sol yarıyı ele: lo = mid + 1. Büyükse sağ yarıyı ele: hi = mid - 1.
5. 05lo, hi'yi geçene kadar tekrarla; aralık boşalırsa değer yoktur.

#Örnek kod

Aynı algoritma 8 dilde. Her program derlenip çalıştırılarak test edildi ve hepsi aynı çıktıyı veriyor.

def binary_search(a: list[int], target: int) -> int:
    """a must be sorted. Returns the index of target, or -1."""
    lo, hi = 0, len(a) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if a[mid] == target:
            return mid
        if a[mid] < target:
            lo = mid + 1  # target is in the right half
        else:
            hi = mid - 1  # target is in the left half
    return -1


numbers = [1, 3, 5, 7, 9, 11]
print(binary_search(numbers, 7))
print(binary_search(numbers, 4))

#Karmaşıklık

n elemanlı dizi en fazla log₂ n + 1 adımda tek elemana iner: 1.000 eleman için 10, 1.000.000 eleman için 20 karşılaştırma. Döngüyle yazılan sürüm ek bellek kullanmaz; özyinelemeli sürüm O(log n) yığın belleği kullanır. Dikkat: mid hesaplanırken çok büyük dizilerde (lo + hi) taşabilir; lo + (hi - lo) / 2 daha güvenlidir.

#Ne zaman kullanılır?

Sıralı verilerde tekrar tekrar arama yapılacaksa vazgeçilmezdir: veritabanı indeksleri, sözlükler, sıralı dizilerde arama (Java'da Arrays.binarySearch, Python'da bisect). Aynı fikir "cevap üzerinde ikili arama" adıyla optimizasyon problemlerinde de kullanılır. Veri sık değişiyor ve sıralı tutulamıyorsa hash tablosu ya da dengeli ağaçlar daha uygundur.

#Alıştırma

Soruları cevaplamak ve ilerlemeni kaydetmek için giriş yap.

#Bundan sonra

Bu dersi bildiğini varsayan dersler:

• İkili Arama Ağacı (BST)
• Üstel Arama (Exponential Search)
• Enterpolasyon Araması
• Atlamalı Arama (Jump Search)