Sıralı Dizilerde İkili Arama (Binary Search)
Daha önce dizileri
sıralamak için
şurada Arrays sınıfının
sort() metodundan faydalanmıştık. Dizilerde bir başka sıkça kullandığımız işlem de dizinin değerleri içinde
arama yapmaktır. Bu amaçla Arrays sınıfında yer alan
binarySearch() metodlarını kullanabiliriz. Bu
ikili arama metodlarını kullanmak için dizinin sıralı olması gerekmektedir. Eğer dizi sıralı değil ise
sort() metodunu kullanarak sıralama yapabiliriz.
Sıralı bir dizide
ikili arama yapmak aradığımız sayıya hızlı bir şekilde ulaşmamızı sağlayacaktır. Eğer sıralı bir dizide 10 adet sayı varsa en kötü ihtimal ile 4 adımda sayıyı bulacaktır. Benzer olarak 500000 elemanlı bir dizide istenen sayıya ulaşma en kötü ihtimalle 19 adımda gerçekleşecektir.
Binary Search (ikili arama) görüldüğü gibi ciddi oranda arama uzayını küçültmekte, arama programının
karmaşıklığını azalatmaktadır.
Adım sayısının en kötü ihtimalini şu formülle bulabiliriz:
N: Dizinin eleman sayısı olsun
O(N): N elemanlı dizinin karmaşıklığı (en kötü ihtimalli adım sayısı) olsun
O(N)=(logN) + 1'dir. Buradaki logaritma 2 tabanındadır. 10 tabanlı logaritma üzerinden işlem yapılacaksa şu denklem kullanılabilir:
O(N)=((logN) / (log2)) + 1'dir. Buradaki logaritmalar 10 tabanlıdır (burada tam sayı, integer, bölmesi yapılıyor).
Örnek bir
ikili arama kodu şu şekildedir:
/**
* Bu metot verilen dizide sayi değişkeninin değerini arar ve
* dizideki yer aldığı indisini bulur
* @param dizi int[] : Sıralı dizimiz
* @param sayi int : Aranacak değer
* @return int : Dizide bulunduğu yer
*/
public int ikiliAra(
int[] dizi,
int sayi) {
int index;
// elemanın bulunacağı indis
index =
Arrays.binarySearch(dizi, d);
return index;
}
Yapılan aramada eğer sayı dizide yer almıyor ise bulunamadı anlamında -1 değeri dönülecektir.
Imza: admin 
