Binary Search(Ikili Arama) :
- İkili arama sıralanmış listeler üzerinde etkili bir şekilde çalışan bir arama algoritmasıdır.
- Binary search böl ve fethet yaklaşımını takip eden bir algoritmadır.
- En iyi durum zaman karmaşıklığı O(1) , En kötü durum zaman karmaşıklığı O(logn)
- Binary search sıralı diziler üzerinde uygulanabilir , eğer ki listedeki elemanlar sıralı değilse öncelikle onları sıralamak zorundayız.
C dilinde kodlamasına bakacak olursak : Kodların içerisine yorum satırını da ekledim.Her şey tek tek açıklandı umarım anlaşılır olmuştur.
#include<stdio.h>
#include<stdlib.h>
int binarySearch(int dizi[],int N,int aranan){
// sag demek son index değerini atıyoruz dizi uzunluğu-1
// sol baştaki index değeri 0
int sol=0,sag=N-1,orta;
while(sol<=sag){
// orta degerimizi buluyoruz
orta=(sag+sol)/2;
// ortadaki indexde aranan var mı ?
if(dizi[orta]==aranan){
return orta;
}
// yoksa eğer ve dizinin orta indexindeki değer aranandan büyükse
else if(dizi[orta]>aranan){
// aranan sol tarafta kaldığı için sagı bir azaltıyoruz ve orta değerini küçültüyoruz üstte sag+sol/2 yaptığımız için
sag=orta-1;
}else{
// aranan sağ tarafta kaldığı için solu bir arttırıyoruz ve orta değerini büyültüyoruz.
sol=orta+1;
}
}
return -1;
}int main(){
int aranan;
// sorted(sıralanmış) dizi
int dizi[] = {1,9,10,15,88};
// 20 / 4 = 5 , dizi uzunlugunu verir.
int diziUzunlugu = sizeof(dizi)/sizeof(dizi[0]);
printf("Aranilan sayi : ");
scanf("%d",&aranan);
int bulunduMu = binarySearch(dizi,diziUzunlugu,aranan);
bulunduMu != -1 ? printf("%d.indexte bulundu ",bulunduMu) : printf("Eleman dizide bulunmadı!");
return 0;
}