İkili arama algoritması nasıl çalışır?

İkili arama, sıralanmış bir diziyi analiz ederek ve arama aralığını sürekli olarak ortadan bölerek çalışır.

1. Başlatma: Arama aralığının sol ve sağ sınırları belirlenir (genellikle dizinin başlangıcı ve sonu).
2. Karşılaştırma: Aralık ortasının indeksi hesaplanır. Bu indeksteki değer, aranan öğeyle karşılaştırılır.
3. Aralığın küçültülmesi:
   • Eğer ortadaki değer arananla uyuşuyorsa, öğe bulunmuştur.
   • Eğer ortadaki değer aranan değerden büyükse, arama sol yarıda devam eder. Sağ sınır ortadan 1 azaltılır.
   • Eğer ortadaki değer aranan değerden küçükse, arama sağ yarıda devam eder. Sol sınır ortadan 1 artırılır.
4. Tekrar: 2 ve 3 adımları, öğe bulunana veya arama aralığı boşalana kadar tekrarlanır.

Algoritmanın karmaşıklığı O(log n) olup, büyük dizilerde doğrusal aramadan çok daha etkilidir.

Python'da örnek uygulama:

def binary_search(arr, target):
    """
    İkili arama uygulaması.
    Sıralanmış bir dizi ve aranan değeri alır.
    Öğenin indeksini veya bulunamazsa -1 döner.
    """
    left, right = 0, len(arr) - 1

    while left <= right:
        mid = (left + right) // 2  # Ortadaki indeks hesaplanır
        mid_val = arr[mid]      # Ortadaki değer alınır

        if mid_val == target:
            return mid  # Öğe bulundu
        elif mid_val < target:
            left = mid + 1  # Aranan büyük, sağda arama
        else: # mid_val > target
            right = mid - 1 # Aranan küçük, solda arama

    return -1 # Öğe bulunamadı