Binary Search Algorithm with TypeScript
Bu yazımda Arama algoritmalarından biri olan İkili Arama ya da Bölerek Arama olarak da bilinen Binary Search Algoritmasını anlatacağım ve TypeScript dili ile nasıl yazarız onu göstereceğim.
Binary Search Algoriması Nedir?
İsminden de anlaşılacağı üzere Binary Search bir arama algoritmasıdır. Küçükten büyüğe veya büyükten küçüğe sıralanmış bir küme sayının içinden kümedeki bir elamanı bu algoritmayı kullanarak bulabiliriz.
Binary Search Algoritması Nasıl Çalışır?
Elimizde küçükten büyüğe veya büyükten küçüğe sıralanmış bir küme sayının olduğunu ve bu kümede bir sayıyı arayacağımızı düşünelim. Sayılar sıralı olduğu için arama işleminde ilk olarak kümenin orta noktasındaki elemana bakıyoruz. Bu orta noktadaki elemanın değeri aradığımız elemanın değerinden büyükse orta noktanın sağ tarafında kalan hiçbir elemanla işimiz yok tam tersi ise de orta noktanın sol tarafında kalan hiçbir elemanla işimiz yok. Bu işlemin ardından n tane eleman içinde yapacağımız aramayı n/2 tane elemana indirmiş oluyoruz ve aynı işleme aradığımız elemanın konumunu bulana kadar devam ediyoruz.
* Ali ve Veli isimli iki çocuk var.
* Ali aklından 1 ile 100 aralığında bir sayı tutar. (Ali’ nin tuttuğu sayı : 22)
* Veli bu sayıyı tahmin ederek bulmaya çalışacak. Ali de Veli’ nin sayıyı bulması için tahminlerine Büyük Küçük diyerek yardımcı olacak.
- V : 50.
- A : Küçük.
- V : 25.
- A : Küçük.
- V : 13.
- A : Büyük.
- V : 19.
- A : Büyük.
- V : 22. (Bitti)
let arr : number[] = [1,2,3,4,5,6,7,8,9,10];
let aranan: number = 9;
let sonuc = search(aranan);
if(sonuc == -1){
console.log('Dizide ' + aranan + ' sayısı bulunamamıştır.');
}
else{
console.log('aranan sayinin index numarası : ' + sonuc);
}
// For Loopfunction search(aranacak : number) : number{
let index=-1,i=0,mid,n = arr.length;
for(i; i < arr.length ;i){
mid = i + Math.floor((n - i)/2);
if(arr[mid] < aranacak){
i = mid + 1;
}else if(arr[mid] > aranacak){
n = mid - 1;
i++;
}else{
index = mid;
break;
}
}
return index;
}// While Loopfunction search(aranacak : number) : number {
let index = -1,min = 0,mid,n = arr.length;
let flag : boolean = false;
while(!flag){
if(min >= n){
index = -1;
flag = true;
}
else{
mid = min + Math.floor((n - min)/2);
if(arr[mid] < aranacak){
min = mid + 1;
}else if(arr[mid] > aranacak){
n = mid - 1;
}else{
flag = true;
index = mid;
}
}
}
return index;
}
index değişkeninin ilk değerini -1 olarak tanımlıyorum. Aradığım sayı kümede var ise sayının konumunu bu index değerine atıyorum ve atadığım değeri dönüyorum. Eğer aradığım sayı kümede yok ise -1 değerini dönüyorum.
mid değişkeni referans aldığım değer, yani kümenin orta noktası.
flag değişkeni (While Loop) döngünün kırılması için konulmuş bir bayrak. Sayının bulunma ya da bulunamama durumunda tekrar döngüye girilmemesi için.
Bu yazımda Veri Yapıları için önemli bir konu olan Binary Search Algoritmasının nasıl çalıştığını ve nasıl kodlandığını TypeScript Dili kullanarak anlatmaya çalıştım umarım sizler için yararlı bir yazı olur.
