Sponsor Reklam 


22.10.2008 (04:46)

 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








Yazilar kaynak gosterilmeden kopyalanamaz © www.kodcu.net // Twitter