1-) VERİYAPILARI - İkili arama (binary search)

Arama algoritması, yapı olarak parçala fethet (divide and conquere) yaklaşımının bir uygulamasıdır. Algoritmanın adımları aşağıdaki verilmiştir.

• Problemde aranacak uzayın tam orta noktasına bak
• Şayet aranan değer bulunduysa bit
• Şayet bakılan değer aranan değerden büyükse arama işlemini problem uzayının küçük elamanlarında devam ettir.
• Şayet bakılan değer arana değerden küçükse arama işlemini problem uzayının büyük elemanlarında devam ettir.
• Şayet bakılan aralık 1 veya daha küçükse aranan değer bulunamadı olarak bitir.

Yproblem her seferinde aranan sayıya göre ortadan ikiye bölünmektedir. Bu anlamda problemin log₂(n) adımda çözülmesi beklenir. Burada logaritmik fonksiyonların üssel fonksiyonların tersi olduğu ve her adımda problemi iki parçaya böldüğümüzü hatırlayınız. Algoritmanın başarılı olması için sayıların kendi içinde sıralı olması gerekmektedir.

ÖRN:   int a[10]={2,3,5,6,9,12,32,54,74,111}; dizisinden 3 sayısını arayalım

Bu dizi üzerinde 10 eleman bulunduğuna göre aranan sayı her ne olursa olsun ilk bakılacak değer ortadaki değer olan (5. Değer) 12 sayısıdır. Aşağıdaki açıklamalar sırasında en küçük indis için kırmız, en büyük indis için yeşil ve orta değer için mavi renkler kullanılacaktır. İlk örneğimiz olan 3 sayısını ararken indis değerlerimiz aşağıdaki şekildedir:

Dizide aranan sayının bulunabileceği en küçük indis 0 ve en büyük indis 10 olarak kabul edilirse

Dizide bulunan 5. Sayıya bakıyoruz (10 + 0) / 2 = 5. Ayrıca artık aradığımız sayının 5. Elemandan daha büyük olma ihtimali bulunmuyor. Dolayısıyla aranabilecek en büyük sayı 5. Elemandadır diyerek en büyük indisi dizinin 5. Elemanı olarak ayarlıyoruz.

Arama işlemine ortadaki sayı ile devam edeceğiz (5+0)/2 = 2 olduğu için 2. Elemana bakıyoruz.

Aradığımız sayı baktığımız sayıdan küçük olduğu için artık 5’ten büyük sayılara bakmanın bir anlamı yoktur diyerek en büyük indisi dizinin 2. Elemanı olarak atıyoruz. Baktığımız sayı aradığımız sayıya eşit olduğu için de sayıyı bulduk diyerek çalışmamızı bitiriyoruz.

KOD: