22 NİSAN 2017
CUMARTESİ
11.38
Algoritmalar - İkili Arama Algoritması (Binary Search)

İkili Arama Algoritması (Binary Search), elde bulunan veriyi 2 parçaya bölerek yapılan arama algoritmasıdır. Bu algoritma normal arama işlemlerinde sonuca daha hızlı ulaşmak için kullanılır.

 

Bu makale içerisinde ikili arama algoritması detaylıca incelenecektir. Algoritma mantığını anladığınız taktirde her programlama dilinde rahatlıkla kullanabilir ve sonuca daha hızlı ulaşabilirsiniz. Başlamadan önce yapılacak işlemleri bir pseudo code olarak elimize alalım;

PROBLEM: Elimizde bir dizi bulunmaktadır ve biz bu dizinin içerisindeki bir veriye ulaşmak istiyoruz.

  1. Dizinin ortanca elemanını bulalım.
  2. Eğer aranan değer bulunursa işlemi sonlandıralım.
  3. Eğer ortanca eleman aranan değerden büyükse arama işlemini ortanca değerden küçük alanda devam ettirelim.
  4. Eğer ortanca eleman aranan değerden küçükse arama işlemini ortanca değerden büyük alanda devam ettirelim.
  5. Eğer aranan değer dizi içerisinde bulunmuyorsa bulunmadi ibaresini ekrana yazdıralım.

Sıralı Bir Dizi

Arama yapılacak olan dizi kesinlikle sıralı olmalıdır (1-2-3-4-5 gibi). Çünkü kurduğumuz algoritmaya göre aradığımız sayı ortanca elemandan ya küçük ya büyük olacaktır. Bu durumda sayıyı aradığımız dizi mutlaka sıralı olmalıdır. Eğer veritabanından çektiğimiz bir diziden veya kullanıcıdan alınan verilerden oluşturulan bir dizide bu algoritmayı kullanmak istiyorsak öncelikle diziyi sıralı hale getirmemiz gerekmektedir.

Algoritmayı Çalıştıralım

Üzerinde çalışma yapacağımız kod yapısı C++ olacaktır. Sayfanın en altında PHP dilinde de aynı algoritmayı çalıştıran bir kod yapısı bıraktım.

Öncelikle bir dizi oluşturalım.

int dizi[7] = {1, 5, 9, 12, 17, 23, 44};

Bildiğimiz üzere dizilerde ilk eleman 0. elemandır. İlk adımımıza göre ortanca elemanı bulmalıyız. Bu sebeple ortanca eleman 0+6/2 = 3 olacaktır. Dizinin 3. elemanı ise 12'dir.

Algoritma mantığını anlayabilmek için dizide yer alan 44 sayısına ulaşmaya çalışalım;

Yukarıdaki görselimizde arama yaptığımız dizide 44 sayısını bulana kadar ortanca değerleri aldırdık. Bunu yapmak için oluşturacağımız algoritmamızda başlangıç ve bitiş değerlerini aşağıdaki görselimiz yardımıyla inceleyebiliriz;

Açıklama

Görüldüğü üzere dizinin başlangıç aşamasında 1 ile 44 sayıları (dizinin 0. elemanı ile 6. elemanı) baz alınmış ve ortanca eleman bu elemanların arasında olarak belirlenmiş (0+6/2 = 3).

İkinci aşamasında ise 44 sayısının 12 sayısından büyük olması küçük alanın elenmesi anlamına geldiği için ilk aşamadaki ortanca sayı olan 12 sayısını başlangıç kabul ederek son değerinde herhangi bir değişiklik yapmamış ve yeni arama bölümümüzü sağ tarafa (12 sayısından büyük sayılara) yöneltmiş oluyoruz.İkinci aşamada yeşil ile gösterilen başlangıç değeri 12, dizinin 3. elemanıdır. Dizinin son elemanı olan 6. elemanı ile yeni başlangıç elemanı olan 3. elemanı arasındaki ortanca değer ise (3+6)/2 olarak 4.5 olarak belirlenir. Bu da 5'e yuvarlanır ve yeni ortanca değer 23 kabul edilir. Bulduğumuz 23 değeri aradığımız 44 değerine eşit olmadığı için sonraki aşamaya geçilir.

Üçüncü aşamaya geçtiğimizde, bir önceki aşamada bulduğumuz 23 değeri aradığımız 44 değerinden küçük olduğu için 23 değeri başlangıç kabul edilir ve bitiş değeri olan 6. elemanda herhangi bir değişiklik olmaz. Yeni başlangıç değeri 23, dizinin 5. elemanıdır. Dizinin son elemanı 6. eleman olduğu için (6+5)/2 = 5.5 olarak kabul edilir ve bu da 6'ya yuvarlanır. Yeni ortanca değerimiz olan 6. elemandır. 6. elemanımız olan 44, aradığımız sayı olan 44'e eşit olduğu için işlemimiz bulundu olarak tamamlanır.

Ekstra

Aynı örneği baz alarak aranan değerin olmama durumunu inceleyelim. Örneğin aradığımız değer 18 olsun.

Dizinin başlangıç elemanı ilk örnekte olduğu gibi 1, son elemanı ise 44'tür. Bu sebeple ortanca eleman bulunurken dizinin 0. ve 6. elemanları başlangıç ve son elemanları olduğu için (0+6)/2 = 3 olacak ve dizinin 3. elemanı olan 12 değeri ortanca değer olarak kabul edilecektir.

İkinci aşamada ise aranılan değer olan 18 değeri 12 değerinden büyük olduğu için geride kalan alan elenecek ve yeni çalışma alanı 12'den büyük olan kısımda kalacaktır. Bu alanın başlangıcı ise dizinin 3. elemanı olacak ve bitişte 6. eleman olarak kalacaktır. Dolayısıyla (3+6)/2 = 4.5 olacak ve bu değer 5'e yuvarlanarak yeni ortanca eleman dizinin 5. elemanı kabul edilecektir. Dizinin 5. elemanı ise 23'tür. 23 sayısı aranılan 18 sayısından büyük olduğu için ilerde kalan alan arama alanı dışına atılır.

Üçüncü aşamada ise 2. aşamadaki ortanca değer olan 23 sayısı bitiş elemanı olarak kabul edilir. Başlangıç elemanı olan 12 sayısı ise değişiklik göstermez. Dizinin yeni bitiş elemanı olan 23 sayısı, 5. elemandır. Başlangıç elemanı olan 12 ise dizinin 3. elemanıdır. (3+5)/2 = 4 olduğu için ortanca elemanı dizinin 4. elemanı olan 17 olarak belirlenir. Ne yazık ki aranılan 18 değeri 17'den büyüktür ve bitiş değeri olan 23 ile 17 arasında dizi içerisinde başka bir değere sahip olmadığımız için aranılan 18 sayısı dizide bulunmamaktadır.

C++'ta

int main() {
	int dizi[7] = {1, 5, 9, 12, 17, 23, 44};
	int aranan = 12;
	
	int baslangic = -1;
	int bitis = 7; // 4
	int i;
	bool kontrol = false;
	
	while(bitis-baslangic > 1) {
		i = (baslangic+bitis)/2;
		if(dizi[i] == aranan) {
			kontrol = true;
			cout << aranan << " degeri dizi icerisinde bulunmaktadir.";
			break;
		} else if(dizi[i] > aranan) {
			bitis = i;
		} else if(dizi[i] < aranan) {
			baslangic = i;
		}
	}
	
	if(kontrol == false) {
		cout << aranan << " degeri dizi icerisinde bulunmamaktadir.";
	}
}

PHP'de

<?php
$dizi = array('1', '5', '9', '12', '17', '23', '44');
$aranan = 12;

$baslangic = -1;
$bitis = 7;
$kontrol = false;

while ($bitis-$baslangic > 1) {
	$i = ($baslangic + $bitis)/2; // Ortanca Değer
	if($dizi[$i] == $aranan) {
		$kontrol = true;
		echo $aranan." değer dizi içerisinde <b>bulunmaktadır.</b>";
		break;
	} elseif($dizi[$i] > $aranan) {
		$bitis = $i;
	} elseif($dizi[$i] < $aranan) {
		$baslangic = $i;
	}
}

if($kontrol == false) {
	echo $aranan." değer dizi içerisinde <b>bulunmamaktadır.</b>";
}
?>

Kodları İncelediğimizde;

Başlangıç ve Bitiş adında oluşturduğumuz değişkenlerimiz farkettiğiniz üzere dizinin normal elemanları içerisinde bulunmamaktadır. Yani dizimiz 0. elemandan başlıyor ve 6. elemana kadar devam ediyor. Başlangıç değerimiz ise buna bağlı olarak -1 ve bitiş değerimiz de 7. Bunun sebebi dizinin köşe elemanlarınında bu aramaya katılabilmesidir. Eğer buradaki değerleri 0 ve 6 olarak belirlersek dizinin köşelerinde yer alan elemanlarımız aramaya dahil olmayacaklar ve sonuçta bulunamadı çıktısı alınacaktır.

YORUMLAR 0
Bu konuya henüz kimse yorum yapmadı.
İlk yorumu sen yapmak ister misin?
YORUM BIRAK
Şuanda bu yoruma cevap yazıyorsunuz:
İptal Et