Python’da İkili Arama: Verimli Arama için Eksiksiz Rehber

Genel konuşmak gerekirse, bir algoritma, bir bilgisayarın belirli bir görevi yerine getirmek veya bir problemi çözmek için izlediği kesin talimatlar dizisidir. Makine öğrenmesindeki farklı algoritma türlerini öğrenmek için What is an Algorithm blog yazımıza göz atın.

Kavramsal genel bakış

İkili arama, sıralanmış bir veri kümesinde bir değeri verimli şekilde bulmak için tasarlanmış güçlü bir algoritmadır. İkili aramanın arkasındaki temel fikir basittir: Doğrusal aramada olduğu gibi veri kümesindeki her bir öğeyi tek tek kontrol etmek yerine, ikili arama her adımda arama aralığını yarıya indirir ve süreci çok daha hızlı hale getirir.

Nasıl çalıştığı şöyledir:

1. Aramaya, hedef değeri veri kümesinin ortasındaki öğe ile karşılaştırarak başlayın. Orta değerin dizini şu formülle hesaplanır: middle = (low + high) / 2, burada low mevcut arama aralığındaki ilk öğenin dizinidir, high ise son öğenin dizinidir.
2. Orta değeri hedefle karşılaştırın. Hedef değer orta öğeye eşitse, dizini bulmuşsunuzdur ve arama tamamlanır. Hedef değer orta öğeden küçükse arama veri kümesinin sol yarısında devam eder. Hedef değer daha büyükse arama veri kümesinin sağ yarısında devam eder.
3. 1-2. adımları tekrarlayın. Arama aralığı her adımda sürekli olarak yarıya indirilir. Hedef değer bulunana veya arama aralığı boşalana kadar işlemi yineleyin.

İkili arama süreci. Görsel: Yazar

Yukarıda, ikili aramanın arkasındaki kavramı gösteren basitleştirilmiş bir örnek yer alıyor.

Bu yarıya indirme süreci, ikili aramayı bu kadar verimli kılar. Ancak, ikili aramanın doğru çalışması için veri kümesinin sıralı olması gerektiğini unutmamak önemlidir. Veriler sıralı değilse, algoritma amaçlandığı gibi çalışmaz. 

Aramak isteyebileceğiniz farklı veri yapıları türleri hakkında daha fazla bilgi edinmek için Data Structures: A Comprehensive Guide With Python Examples başlıklı içeriğe göz atın.

Akılda tutulması gereken noktalar

Aşağıdaki noktalar, ikili aramanın temel ilkelerini vurgular.

Verimlilik

İkili arama, özellikle büyük veri kümeleriyle çalışırken, doğrusal aramadan önemli ölçüde daha hızlıdır. Doğrusal aramanın zaman karmaşıklığı en kötü durumda her bir öğeyi kontrol edebileceği anlamına gelen O(n) iken, ikili arama daha verimlidir. Zaman karmaşıklığı O(log n)’dir; bu da arama alanının her adımda yarıya indiği ve gerekli karşılaştırma sayısının önemli ölçüde azaldığı anlamına gelir.

Algoritmaların nasıl değerlendirildiğine dair ayrıntılı bir açıklama için Big O Notation and Time Complexity Guide: Intuition and Math içeriğimize bakın. Bir diğer seçenek olarak Analyzing Complexity of Code through Python öğreticimizden yararlanabilirsiniz.

Gereksinimler

İkili aramanın çalışması için veri kümesinin artan veya azalan düzende sıralanmış olması gerekir. Bu bir gerekliliktir; çünkü algoritma, veri kümesinin hangi yarısında aranacağını belirlemek için öğelerin sırasına dayanır. Veriler sıralı değilse, ikili arama hedef değeri doğru şekilde bulamaz.

Esneklik

İkili arama, yinelemeli veya özyinelemeli bir yaklaşımla uygulanabilir. Yinelemeli yöntemde, arama aralığını defalarca yarıya indirmek için döngüler kullanılır. Özyinelemeli yöntemde ise işlev, daha küçük bir arama aralığıyla kendisini çağırır. Bu esneklik, farklı uygulamalara iyi uyum sağlar.

Gerçek Dünya Uygulamaları

İkili arama güçlü bir araçtır. Arama aralıklarını hızla daraltmadaki verimliliği, özellikle performans ve hızın kritik olduğu büyük veri kümeleriyle çalışırken onu vazgeçilmez kılar. Bazı belirli uygulamaları inceleyelim ve ikili aramanın diğer algoritmalarla nasıl karşılaştırıldığını görelim.

Veritabanları

Veritabanlarında, sıralı alanlardaki kayıtları hızlıca bulmak için ikili arama sıklıkla kullanılır; örneğin, kullanıcı kimliğine göre sıralanmış bir veritabanında belirli bir kullanıcıyı bulmak gibi. Milyonlarca kaydı içeren bir veritabanını düşünün. Doğrusal arama, her kaydın tek tek taranmasını gerektirir ve bu da hatırı sayılır zaman alabilir. Bunun yerine, ikili arama arama alanını sistematik olarak yarıya indirerek istenen kaydı hızla saptar ve gereken karşılaştırma sayısını önemli ölçüde azaltır.

Veri bilimi

Büyük ve sıralı veri kümelerinde arama yapmak, veri biliminde yaygın bir görevdir. Örneğin, zaman serisi analizinde, sıralı olaylar dizisinde belirli zaman damgalarını bulmak için ikili arama kullanılabilir. Makine öğrenmesinde, ikili arama algoritmaları bir aralıktaki en iyi değeri bularak hiperparametreleri optimize etmek için kullanılabilir.

Bilgisayar grafikleri

Bilgisayar grafiklerinde, hassasiyet ve hız gereken algoritmalarda ikili arama kullanılır. Bir örnek, ışığın nesnelerle nasıl etkileştiğini simüle etmek için kullanılan bir işleme tekniği olan ışın izleme (ray tracing)’dir. İkili arama, ışınlar ile yüzeyler arasındaki kesişim noktalarını hızla bulmak için kullanılabilir.

Karmaşık algoritmalar için yapı taşları

İkili arama yalnızca tek başına faydalı olmakla kalmaz; aynı zamanda daha karmaşık algoritmalar ve veri yapıları için bir yapı taşı görevi görür. Örneğin, ikili arama ağaçları (BST) gibi arama ağaçları ve AVL ağaçları gibi dengeli ağaçlar, ikili aramanın ilkelerine dayanır. Bu yapılar, verimli arama, ekleme ve silme işlemlerine olanak tanır; bu da verilerin dinamik olarak güncellenip sık sık aranması gerektiğinde onları kullanışlı kılar. Bu ağaçlar hakkında daha fazla bilgi edinmek için AVL Tree: Complete Guide With Python Implementation içeriğine göz atın.

İkili Arama ve Diğer Arama Algoritmaları

İkili aramanın iki yaygın arama algoritmasıyla, yani doğrusal arama ve karma (hash) bakışıyla nasıl karşılaştırıldığını inceleyelim.

Doğrusal arama

Doğrusal arama, bir veri kümesindeki her öğeyi sırayla inceleyen basit bir algoritmadır. Zaman karmaşıklığı O(n) olduğundan, ikili aramaya kıyasla belirgin şekilde daha az verimlidir. Ancak, doğrusal arama verilerin sıralı olmasını gerektirmez; bu da bazı durumlarda onu kullanışlı kılar.

Karma (hash) bakışı

Karma bakışı, değerlerin benzersiz anahtarlarla ilişkilendirildiği veri kümelerinde hızlıca değer bulmak için kullanılan verimli bir algoritmadır. Anahtara bir karma işlevi uygulanarak, karşılık gelen değerin bir karma tablosunda depolandığı dizin hesaplanır. Bu, çoğu zaman O(1) sürede, değerlerin neredeyse anında getirilmesini sağlar. Ancak, karma bakışı belirli öğeleri bulmada çok hızlı olsa da, karma tablosunu depolamak için ek belleğe ihtiyaç duyar ve bir değer aralığı içinde arama yapmak için uygun değildir; bu tür görevler için ikili arama daha uygundur.

Python’da İkili Aramanın Uygulanması

Python’da basit bir ikili aramayı uygulamanın birkaç yolunu inceleyelim. Ancak önce, üzerinde çalışacağımız basit bir veri kümesi ve arayacağımız bir hedef değer belirlememiz gerekiyor. Aşağıdaki sıralı diziye ve arama hedefine sahip olduğumuzu düşünün:

arr = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
target = 56Altyapı:

Yinelemeli yöntem

Yinelemeli yöntem muhtemelen en anlaşılır yaklaşımdır. Bu yöntemde, hedefi bulana kadar arama aralığını tekrar tekrar ikiye bölmek için bir while döngüsü kullanırız. Bu yöntem, açıklığı ve verimliliği nedeniyle sıklıkla tercih edilir.

İkili aramayı yinelemeli olarak şöyle uygulayabilirsiniz:

def binary_search_iterative(arr, target):
    # Define the search bounds
    left, right = 0, len(arr) - 1  
    while left <= right:
        # Calculate the middle index
        mid = left + (right - left) // 2  
        # If the middle element is the target, return its index
        if arr[mid] == target:
            return mid  
        # If the target is bigger, narrow the search to the right half
        elif arr[mid] < target: 
            left = mid + 1  
        # If the target is smaller, narrow the search to the left half
        else: 
            right = mid - 1  
    # Return -1 if the target is not found
    return -1 
    
# Run the iterative function
result = binary_search_iterative(arr, target)
if result != -1:
    print(f"Iterative: Target found at index {result}")
else:
    print("Iterative: Target not found")Altyapı:

Bu koda daha yakından bakalım:

• ‘left’ ve ‘right’ değerlerini arama alanının sınırları olarak belirleyerek başlarız. Başlangıçta left 0’dır (dizinin başı) ve ‘right’ len(arr) - 1’dir (dizinin sonu).

• Her yinelemede, mevcut arama aralığının ortasını temsil eden mid dizinini hesaplarız. Bu, mid = left + (right - left) /2 formülüyle yapılır.

• Daha sonra mid konumundaki öğeyi target ile karşılaştırırız:

• Eşleşiyorlarsa, hedefi bulmuşuzdur ve işlev mid değerini döndürür.

• mid’deki öğe hedeften küçükse, hedef sağ yarıda demektir; bu yüzden left değerini mid + 1 olarak ayarlarız.

• mid’deki öğe hedeften büyükse, hedef sol yarıdadır; bu yüzden right’ı mid - 1 olarak ayarlarız.

• Döngü, hedef bulunana kadar veya left değeri right’ı aşana kadar devam eder; bu da hedefin dizide olmadığı anlamına gelir.

Özyinelemeli yöntem

İkili arama için özyinelemeli yöntem, bu algoritmayı uygulamanın başka bir yoludur. Döngü kullanmak yerine işlev, hedefi bulana veya hedefin mevcut olmadığını belirleyene kadar her seferinde arama sınırlarını ayarlayarak kendisini çağırır.

İkili aramayı özyinelemeli olarak şöyle uygulayabilirsiniz:

def binary_search_recursive(arr, target, left, right):
    # If the search bounds cross, the target isn't in the array
    if left > right:  
        return -1
    # Calculate the middle index
    mid = left + (right - left) // 2 
    # If middle value equals the target, return the index
    if arr[mid] == target: 
        return mid  
    # If the target is bigger than the middle value, search in the right half
    elif arr[mid] < target: 
        return binary_search_recursive(arr, target, mid + 1, right)  
    # If the target is smaller than the middle value, search in the left half
    else: 
        return binary_search_recursive(arr, target, left, mid - 1)  

# Run the recursive function
result = binary_search_recursive(arr, target, 0, len(arr) - 1)

if result != -1:
    print(f"Iterative: Target found at index {result}")
else:
    print("Iterative: Target not found")Altyapı:

Bu koda daha yakından bakalım:

• Özyinelemeli işlev, yinelemeli işlevle aynı başlangıç left ve right sınırlarıyla başlar.

• left’in right’ı aşıp aşmadığını önce kontrol eder. Aşıyorsa, hedefin dizide olmadığını belirten -1 döndürür.

• Aksi halde, işlev mid dizinini hesaplar ve hedefi mid konumundaki öğe ile karşılaştırır.

• Hedef, mid’deki öğeye eşitse, işlev mid’i döndürür.

• Hedef mid’den büyükse, işlev sağ yarıyı aramak için güncellenmiş sınırlarla kendisini özyinelemeli olarak çağırır.

• Hedef mid’den küçükse, işlev sol yarıyı arar.

• Özyineleme, hedefi bulana veya arama alanını tüketene kadar devam eder.

Özyinelemeli işlevler hakkında daha fazlası için Understanding Recursive Functions in Python içeriğine göz atın.

Python’un yerleşik bisect modülünü kullanma

Python’un standart kitaplığı, önceden uygulanmış ikili arama işlevleri sağlayan bisect modülünü içerir. Bu modül oldukça verimlidir ve çoğu zaman kendi işlevimizi yazmaya kıyasla bize zaman kazandırabilir.

Dizimizde hedefi bulmak için bisect modülünü şöyle kullanabiliriz:

# Import the bisect module
import bisect 

# Call the module and provide the array and the target value
index = bisect.bisect_left(arr, target) 

#Print results
if index < len(arr) and arr[index] == target:
    print(f"Bisect: Target found at index {index}")
else:
    print("Bisect: Target not found")Altyapı:

Bu koda daha yakından bakalım:

• bisect_left işlevi, dizinin sırasını korumak için hedefin yerleştirilmesi gereken dizini döndürür. Hedef bu dizinde bulunursa, hedefin dizide mevcut olduğu anlamına gelir.

• Bu yöntem, sıralı dizilerle çalışırken özellikle kullanışlıdır ve sıralı düzeni koruyarak öğe eklemek için de kullanılabilir.

• bisect modülü ayrıca, yerleştirme noktalarını bulmak veya öğeleri doğrudan eklemek için kullanılabilen bisect_right ve insort gibi diğer işlevleri de sağlar.

Zaman ve Bellek Karmaşıklığı

Bir algoritmanın verimliliğini tartışırken, çoğu zaman çalışma süresinin veya bellek gereksinimlerinin giriş boyutu arttıkça nasıl büyüdüğünü tanımlamak için O(x) şeklinde gösterilen Big O gösterimini kullanırız. İkili aramada zaman karmaşıklığı tipik olarak O(log n)’dir. Bu, veri kümesi büyüdükçe hedefi bulmak için gereken işlem sayısının logaritmik olarak arttığı ve ikili aramayı büyük veri kümeleri için dahi verimli kıldığı anlamına gelir.

İkili aramanın yinelemeli yönteminin zaman karmaşıklığı, arama aralığı her yinelemede yarıya indirildiği için O(log n)’dir. Bellek karmaşıklığı ise O(1)’dir; çünkü arama sınırlarını ve orta öğeyi izlemek için yalnızca birkaç değişken gerektiren sabit miktarda ek bellek kullanır.

Özyinelemeli yöntemin de aynı nedenle zaman karmaşıklığı O(log n)’dir. Ancak, her özyinelemeli çağrı için çağrı yığınına yer ayrılması gerektiğinden, bellek karmaşıklığı O(log n)’dir. Her özyinelemeli çağrı yığına bir katman eklediğinden, özyineleme derinliği, veri kümesinin boyutuyla ilişkili olarak logaritmiktir.

Her iki yöntem de zaman açısından verimli olsa da, yinelemeli yaklaşım bellek açısından daha verimlidir. Bu nedenle bisect modülü perde arkasında yinelemeli bir yaklaşım kullanır. Ben de bu nedenle yinelemeli yaklaşımı tercih ediyorum. Ancak, özyinelemeli yaklaşım bazı kişiler için daha sezgisel olabilir ve daha az satır kod gerektirebilir.

Yaygın Tuzaklar ve Bunlardan Kaçınma Yolları

İkili arama kullanırken dikkat edilmesi gereken birkaç yaygın tuzak vardır. Bunlar algoritmanızın doğruluğunu ve verimliliğini etkileyebilir; bu yüzden not etmek önemlidir.

Öncelikle, ikili arama veri kümesinin sıralı olmasına dayanır. Veriler sıralı değilse, ikili arama doğru çalışmaz; yanlış sonuçlar döndürebilir veya tamamen başarısız olabilir. Bu nedenle, ikili aramayı uygulamadan önce veri setimizi sıralamak şarttır. Verileri sıralamak mümkün değilse, ikili arama uygun bir araç değildir.

Sık karşılaşılan bir sorun da bir-birim (off-by-one) hatalarıdır. Dizin hesaplamalarının biraz hatalı olması durumunda ortaya çıkan bu hatalar, sonsuz döngülere veya hedef değerin bulunamamasına yol açabilir. Bu, orta nokta hesaplaması veya sınır ayarlamaları hassas şekilde ele alınmadığında meydana gelebilir. Bunu önlemek için, orta dizin hesaplamalarının doğru olduğundan ve her karşılaştırmadan sonra sınırların düzgün biçimde güncellendiğinden emin olun. Unutmayın, Python’da dizin değerleri 1’den değil 0’dan başlar.

İkili aramayı özyinelemeli kullanıyorsanız dikkat edilmesi gereken bir diğer zorluk da özyineleme derinliği sorunlarıdır. Python’da, aşırı bellek kullanımını önlemek için yapılabilecek özyinelemeli çağrı sayısına bir sınır vardır. Veri kümeniz çok büyükse, derin özyineleme bu sınırı aşarak yığın taşmasına neden olabilir. Bunu hafifletmek için, özyineleme derinliği sınırlamalarından etkilenmeyen yinelemeli yaklaşımı düşünün. Özyineleme tercih ediliyorsa veya gerekliyse, sys.setrecursionlimit() kullanarak özyineleme sınırını artırabilirsiniz; ancak bu, diğer olası sorunlardan kaçınmak için dikkatle yapılmalıdır.

Sonuç

İkili arama, her Python geliştiricisinin araç setinde bulunması gereken güçlü ve verimli bir algoritmadır. Yinelemeli veya özyinelemeli olarak uygulansın, özellikle büyük veri kümelerinde doğrusal aramaya kıyasla önemli bir performans avantajı sunar. Daha fazlası için DataCamp’in Python Programming beceri yoluna veya Software Engineering Principles in Python etkileşimli kursuna göz atın.