EXAMPLE ile İkili Arama Algoritması

İkili aramayı öğrenmeden önce ş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ıralanmış bir öğe listesinden veri bulup getiren gelişmiş bir arama algoritması türüdür. Temel çalışma prensibi, gerekli değer bulunup 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 süreci, sıralanmış veri dizisinin ortadaki öğesinin bulunmasıyla başlar.
• Bundan sonra anahtar değer elemanla karşılaştırılır.
• Anahtar değer ortadaki öğeden küçükse arama, karşılaştırma ve eşleştirme için üst değerleri orta öğeye göre analiz eder
• Anahtar değerin ortadaki öğeden büyük olması durumunda arama, karşılaştırma ve eşleştirme için daha düşük değerleri ortadaki öğeye göre analiz eder

Ö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 – 9 arası indeks ile işaretlenmiştir. Artık dizinin ortası hesaplanır. Bunun için endeksin en soldaki ve en sağdaki değerlerini alıp 2'ye bölüyorsunuz. Sonuç 4.5 ama taban değerini alıyoruz. Dolayısıyla ortadaki sayı 4'tür.
3. Algoritma tüm öğeleri ortadaki (4) en alt sınıra düşürür çünkü 59, 24'ten büyüktür ve artık dizide yalnızca 5 öğe kalır.
4. Şimdi 59, 45'ten büyük ve 63'ten küçüktür. Ortadaki 7'dir. Dolayısıyla sağdaki indeks değeri orta - 1 olur, yani 6 olur ve soldaki indeks değeri öncekiyle aynı yani 5 olur.
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 aramanın nasıl çalıştığını 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 4 olan orta değerden büyüktür.
3. Orta değerden küçük dizi değerleri aramadan çıkarılır ve orta değer 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?

Aşağıdaki nedenler ikili aramayı bir arama algoritması olarak kullanmak için daha iyi bir seçim haline getirir:

• İkili arama, verinin boyutu ne olursa olsun sıralanmış veriler üzerinde 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ını kullanmak yerine sıralama ilkesine dayalı olarak sıralanmış verilerin karşılaştırmalarını gerçekleştirir.
• Her arama döngüsünden sonra algoritma dizinin boyutunu ikiye böler, dolayısıyla bir sonraki yinelemede dizinin yalnızca geri kalan yarısında çalışacaktır.

Bir sonraki eğitimimizi öğrenin Doğrusal Arama: Python, C++ Örnek E-posta

ÖZET

• Arama, kullanıcının belgeleri, dosyaları ve diğer veri türlerini aramasını sağlayan bir yardımcı programdır. İkili arama, sıralanmış bir öğe listesinden veri bulup getiren gelişmiş bir arama algoritması türüdür.
• İkili arama genellikle yarım aralıklı arama veya logaritmik arama olarak bilinir.
• Gerekli elemanın bulunduğu her yinelemede diziyi ikiye bölerek çalışır.
• The ikili algoritma En soldaki ve en sağdaki indeks değerlerinin toplamını 2'ye bölerek dizinin ortasını alır. Artık algoritma, bulunacak elemana bağlı olarak elemanların alt veya üst sınırını dizinin ortasından düşürür.
• 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, yavaş ve hatalı eşitlik karşılaştırmaları kullanmak yerine, sıralama ilkesine dayalı olarak sıralanmış verilerin karşılaştırmalarını gerçekleştirir.
• Sıralanmamış veriler için ikili arama uygun değildir.