Python İkili Arama Algoritması

Sıralanmış listeleri logaritmik O(log n) süresine göre arayın. Adım adım mantık, uç durumlar ve optimizasyonlar da dahil olmak üzere Python'da ikili aramayı çalıştırın ve anlayın.

Editör'de deneyin

Genel Bakış

İkili arama, sıralanmış bir listedeki bir öğeyi bulmak için son derece etkili bir algoritmadır. Her öğeyi O(n) zamanında sırayla tarayan doğrusal aramanın aksine, ikili arama, arama aralığını tekrar tekrar ikiye bölerek çalışır.

Arama, dizinin ortadaki öğesinin incelenmesiyle başlar. Hedef değer ortadaki öğeyle eşleşirse konumu döndürülür. Hedef daha küçükse algoritma aramasını alt yarıya kadar daraltır; hedef daha büyükse üst yarıya kadar daraltır. Bu işlem, öğe bulunana veya alt dizi boyutu sıfıra düşene kadar tekrarlanır.

Python'da ikili aramayı uygulamak için, aktif arama sınırlarını izlemek üzere iki işaretçi (düşük ve yüksek) kullanırız. Arama alanı her adımda yarı yarıya azaldığından, algoritma O(log n) zamanında yürütülür ve bu da onu büyük veritabanları için ideal kılar.

Kod ve Yürütme Çıkışı

Sıralanmış bir listedeki hedef öğenin dizinini döndüren standart yinelemeli ikili arama uygulaması.

binary_search.py

Editör'de deneyin

def binary_search(arr, target):
    low = 0
    high = len(arr) - 1
    
    while low <= high:
        mid = (low + high) // 2
        guess = arr[mid]
        
        if guess == target:
            return mid
        if guess > target:
            high = mid - 1
        else:
            low = mid + 1
            
    return -1

# Sorted test dataset
data = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
target_val = 23

index = binary_search(data, target_val)
print(f"Dataset: {data}")
print(f"Target: {target_val}")
if index != -1:
    print(f"Target found at index: {index}")
else:
    print("Target not found in dataset")

Terminal Çıkışı

Dataset: [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
Target: 23
Target found at index: 5

Adım Adım Uygulama

Veritabanı tablolarında sorgu indeksleme ve arama
Sürekli matematiksel aralıklarda eşik veya sınır değerlerini bulma
Metin alanlarında otomatik tamamlama ve arama işlevleri

Sıkça Sorulan Sorular

İkili aramanın çalışması için listenin sıralanması gerekiyor mu?

Evet, ikili arama kesinlikle sıralanan öğelere dayanır. Liste sıralanmamışsa karşılaştırma mantığı bozulur ve önce listeyi sıralamanız veya doğrusal bir arama kullanmanız gerekir.

Neden özyinelemeli ikili arama yerine yinelemeli ikili arama kullanılmalı?

Özyinelemeli ikili arama zarif olsa da üretimde yinelemeli ikili arama sıklıkla tercih edilir. Yinelemeli yaklaşım O(1) yardımcı alanında çalışır, yinelemeli arama ise çağrı yığını nedeniyle O(log n) alanı kaplar ve aşırı büyük girişlerde yığın taşması riskini taşır.

İlgili Konular

Python Sıralama Algoritmaları

Python sıralama algoritmalarını keşfedin. Kabarcık sıralamasını görselleştirin ve bir tarayıcı IDE bağlamında yerel olarak birleştirme sıralamasını yapın.

Python Birleştirme Sıralama Algoritması Eğitimi

Python'da Birleştirme Sıralamasını nasıl uygulayacağınızı öğrenin. Böl ve Fethet sıralama stratejisinin etkileşimli, adım adım bir örneği.

Python Hızlı Sıralama Algoritması Kılavuzu

Python'daki hızlı sıralama algoritmasını keşfedin. Bu etkileşimli kodlama örneğinde pivot seçimini, bölümlendirmeyi ve yinelemeyi öğrenin.