İkili arama, arama algoritmaların temelini oluşturmaktadır. Algoritmalar konusunda sık sık karşımıza çıkmakta olan ikili arama algoritmasını inceleyelim.
Örneğin bir sayı dizisini ele alalım. Her adımda gerçekleşmek üzere, diziyi ikiye bölerek ilerlemektedir. Parçala fethet mantığı ile çalışmakta olan algoritmamız yalnızca diziler üzerinde değil, birçok problemin çözümünde kullanılmaktadır. Kabaca algoritmadan bahsedecek olursak:
– Dizinin ortasını bul
– Aranan değer mi ? (çık veya devam et)
– Aranan değer küçükse alt parçaya git, büyükse üst parçaya git
– Aralık 1 değeri veya 1 den küçükse sonlandır.
şeklinde ilerlemektedir. Algoritmanın tam verimle çalışabilmesi için sayı dizisinin sıralı olması gerekmektedir.
Örnek bir dizi olarak aşağıdaki diziyi alalım ve 10 elamanını arayalım:
[0 10 20 30 40 50 60 70 80 90]
bu dizide ilk olarak bakılacak eleman 50 ‘dir
10 < 50 şartı sağlandığı için dizinin alt değerlerine bakılır. Bundan sonra üzerine çalışılacak elamanlar
[0 10 20 30 40]
şeklindedir. Yeniden ortadaki değere bakılır. Bu sefer ortadaki terim 20 ‘dir. 10 < 20 şartı sağlandığı için ortadan ikiye bölünen dizinin alt tarafına bakılmaya devam edilir. Bu sefer ki arama yapacağımız dizimiz
[0 10]
şeklindedir. Aradığımız eleman 1 indisli olan 10 = 10 şartını sağladığı için algoritmamız burada sonlanmaktadır. Aranan elaman dizide bulunduğu ve dizinin sıralı olduğu taktirde istenen sonucu elde edebiliyoruz. Anlaşılması ve kodlanması açısından kolay olan bir algoritma olması sebebiyle örneklerde ve günlük hayatta sık sık tercih edilmektedir. En iyi durumda algoritmanın ilk seferde aradığı elamanı bulmasıdır 1 adımda gerçekleşir. Öte yandan sıralı olmayan bir dizinin ilk önce sıralama algoritmaları kullanılarak sıralanması gerekmektedir. Maliyet kullanılan sıralama algoritmasına göre değişecektir. Hızlı Sıralama (Quick Sort) kullanılarak ikili arama algoritması n log_2 (n)+ log_2 (n) adımda gerçekleşir.
Algoritmanın örnek C kodu aşağıda verilmiştir:
