EXAMPLE ile İkili Arama Algoritması

İkili arama algoritmasını öğrenmeden önce, aramanın ne olduğunu öğrenelim.

Arama Nedir?

Arama, kullanıcının bir veritabanında tutulan belgeleri, dosyaları, medyayı veya diğer türdeki verileri bulmasını sağlayan bir yardımcı programdır. Arama, kriterlerin kayıtlarla eşleştirilip kullanıcıya gösterilmesi basit prensibiyle çalışır. Bu şekilde en temel arama fonksiyonu çalışır.

İkili Arama nedir?

İkili arama, sıralı bir listeden veri bulan ve getiren gelişmiş bir arama algoritmasıdır. Temel çalışma prensibi, gerekli değer bulunana ve arama sonucunda kullanıcıya gösterilene kadar listedeki verileri ikiye bölmeyi içerir. İkili arama yaygın olarak şu şekilde bilinir: yarım aralıklı arama ya da logaritmik arama.

İkili Arama Nasıl Çalışır?

İkili arama şu şekilde çalışır:

• Arama işlemi, sıralanmış veri dizisinin orta elemanını bularak başlar.
• Daha sonra, anahtar değeri öğeyle karşılaştırılır.
• Anahtar değer ortadaki elemandan küçükse, arama işlemi karşılaştırma ve eşleştirme için ortadaki elemanın üstündeki değerleri analiz eder.
• Anahtar değer ortadaki değerden büyükse, arama işlemi karşılaştırma ve eşleştirme için ortadaki değerden daha düşük değerleri analiz eder.

İkili Arama Algoritması (Sözde Kod)

İkili arama, kısa ve yinelemeli bir rutin olarak yazılabilir. Düşük ve yüksek olmak üzere iki işaretçi tutar ve hedef bulunana veya aralık boşalana kadar aralığı daraltır.

binarySearch(array, target)
    low = 0
    high = length(array) - 1
    while low <= high
        mid = (low + high) / 2      // floor value
        if array[mid] == target
            return mid
        else if array[mid] < target
            low = mid + 1
        else
            high = mid - 1
    return -1              // target not found

Bu rutin, başarılı olduğunda hedefin indeksini, değer bulunmadığında ise -1 değerini döndürür. Aralık her geçişte yarıya indiği için, döngü en fazla log₂(n) kez çalışır.

Örnek İkili Arama

Bir sözlük örneğine bakalım. Belirli bir kelimeyi bulmanız gerekiyorsa, kimse her kelimeyi sırayla incelemez, ancak gerekli kelimeyi aramak için en yakın kelimeleri rastgele bulur.

Yukarıdaki görsel aşağıdakileri göstermektedir:

1. 10 basamaklı bir diziniz var ve 59 numaralı elemanın bulunması gerekiyor.
2. Tüm elemanlar 0'dan 9'a kadar indekslerle işaretlenmiştir. Şimdi dizinin ortasını hesaplıyoruz. Bunu yapmak için, indeksin en soldaki ve en sağdaki değerlerini alıp 2'ye bölüyoruz. Sonuç 4.5, ancak biz taban değerini alıyoruz. Bu nedenle orta nokta 4'tür.
3. Algoritma, 59'un 24'ten büyük olması nedeniyle ortadaki (4) elemandan en düşük sınıra kadar olan tüm elemanları atar ve dizide artık sadece 5 eleman kalır.
4. Şimdi, 59, 45'ten büyük ve 63'ten küçüktür. Ortadaki sayı 7'dir. Dolayısıyla sağdaki indeks değeri ortadaki sayının eksi 1'i olur, bu da 6'ya eşittir ve soldaki indeks değeri ise önceki gibi kalır, yani 5'tir.
5. Bu noktada 59'ten sonra 45'un geldiğini biliyorsunuz. Dolayısıyla soldaki 5 olan indeks de orta oluyor.
6. Bu yinelemeler, dizi yalnızca bir öğeye indirgenene veya bulunacak öğe dizinin ortası haline gelinceye kadar devam eder.

Örnek 2

İkili arama algoritmasının çalışma prensibini anlamak için aşağıdaki örneğe bakalım.

1. 2 ile 20 arasında değişen bir sıralanmış değer diziniz var ve 18'i bulmanız gerekiyor.
2. Alt ve üst sınırların ortalaması (l + r) / 2 = 4'tür. Aranan değer, orta değer olan 4'ten büyüktür.
3. Arama sonuçlarında orta değerden küçük değerler çıkarılır ve orta değer olan 4'ten büyük değerler aranır.
4. Bu, aranacak gerçek öğe bulunana kadar tekrarlanan bir bölme işlemidir.

Neden İkili Aramaya İhtiyacımız Var?

İkili arama algoritmasının arama algoritması olarak kullanılmasını daha iyi kılan nedenler şunlardır:

• İkili arama, verinin boyutu ne olursa olsun, sıralı verilerde verimli bir şekilde çalışır.
• Aramayı veriyi sırayla tarayarak yapmak yerine, ikili algoritma gerekli öğeyi bulmak için verilere rastgele erişir. Bu, arama döngülerini daha kısa ve daha doğru hale getirir.
• İkili arama, daha yavaş ve çoğunlukla hatalı olan eşitlik karşılaştırmaları yerine, sıralanmış verilerin bir sıralama ilkesine göre karşılaştırmalarını gerçekleştirir.
• Arama işleminin her döngüsünden sonra, algoritma dizinin boyutunu ikiye böler; bu nedenle, bir sonraki yinelemede yalnızca dizinin kalan yarısında çalışacaktır.

Bir sonraki eğitimimize katılın Doğrusal Arama: Python, C++ Örnek E-posta.

İkili Arama ve Doğrusal Arama Karşılaştırması

İkili arama ve doğrusal arama, bir koleksiyondaki bir değeri bulmanın en yaygın iki yoludur. Aşağıdaki tablo, aralarındaki farkları göstermektedir:

Özetle, ikili arama büyük ve sıralı verilerde çok daha hızlıdır, doğrusal arama ise daha basittir ve veriler sıralı olmadığında tek seçenektir.

SSS