C Programlama Ders 10.3 Dizilerde Arama - II - Binary Search

İngilizce ATC ATK Nimonik Kalıcı Kelime Öğrenme Mobil Uygulamaları ve Dil Kartları:

Bu videoda C Programlama Dersinde Binary Search konusunu inceliyoruz.

Bu videoda ilgili konular:
Binary search ( Dizilerde arama ).

[yunusemredursun]

sayılar int tipinde ortalama aldığı için float tipinde olması lazım çünkü virgüllü sayılar geliyo ondan bulamadı

[mehmetnejataydin]

Bu _binary search_ değil. _Binary search_ algoritmasında her adımda dizi elemanlarının yarısının elimine edilmesi gerekir, ki zamansal karmaşıklığı (time complexity) O(log n) olsun. Bu da sağ ve sol indislerin her adımda orta indise göre pozisyon almasıyla mümkündür (mesela, solindis = ortaindis + 1 veya sagindis = ortaindis - 1 gibi).
Videodaki kodda sağ ve sol indisler 1 arttırılıyor veya eksiltiliyor. Böylece her adımda dizinin 1 veya 2 elemanı elimine ediliyor. Bu ise, algoritmanın zamansal karmaşıklığının O(n) mertebesinde olduğu anlamına geliyor. Yani bu kod zamansal karmaşıklık bakımından bir _linear search_ algoritmasına eşdeğer.

[melihtuncay]

#include <stdio.h>
#include <stdlib.h>
int main(){
int i, gecici, j;
int *p;
int eleman;
printf("kac sayi arasindan arama yapacaksin:");
scanf("%d", &eleman);
p=calloc(eleman, sizeof(int));
for(i=0;i<eleman;i++)
{
printf("%d. elemani giriniz:", i+1);
scanf("%d", &p[i]);
}
for(i=0;i<eleman-1;i++){
for(j=eleman-1;j>i;j--){
if(p[j]<p[j-1]){

gecici = p[ j -1 ];
p[ j - 1 ] = p[ j ];
p[ j ] = gecici;
}
}
}
printf("sayilarin siralanmis hali\n");
for(i=0;i<eleman;i++){
printf("%d ", p[i]);
}
printf("\n");


int sol=0, sag, aranan, orta, bulundu=1;
sag=eleman-1;
printf("aranan sayiyi giriniz:");
scanf("%d", &aranan);
i=0;
while(i<eleman){
i++;
orta=(sol+sag)/2;
if(aranan==p[orta]){
printf("%d sayisi %d. indekste bulunmustur", aranan, orta);
return 0;
}
else if(aranan<p[orta]){
sag--;
}
else if(aranan>p[orta]){
sol++;
}
}
printf("%d sayisi bulunamamistir", aranan);
free(p);
return 0;
}