Özdevingen (recursive) fonksiyon ile ikili arama metodu

Bu yazıda binary (ikili) arama algoritmasının isme göre arama yapılmasını recursive (özdevingen) fonksiyon ile yazılmasının C programlama dilinde nasıl yapıldığını anlatmaya çalışacağım.

Recursive Fonksiyon

• Kendini doğrudan veya dolaylı olarak çağıran fonksiyonlara recursive (özdevingen) fonksiyonlar adı verilir.
• Recursive (özdevingen), iterasyonun (döngüler, tekrar) yerine geçebilecek çok güçlü bir programlama tekniğidir.
• Orijinal problemin küçük parçalarını çözmek için, bir alt programın kendi kendini çağırmasını sağlayarak, tekrarlı işlemlerin çözümüne farklı bir bakış açısı getirir.

İkili Arama

İkili Arama, sıralı bir dizide, belirli değerin bulunmasına yönelik bir algoritmadır. Bu teknikteki her bir adımda, aranan değerin, dizinin orta değerine eşit olup olmadığı kontrol edilir. Eşit olmaması durumunda aranan değerin orta değer tarafından ikiye ayrılan kısımlardan hangisinde olduğu kontrol edilir, aranan değeri içeren kısım bir sonraki adımda arama yapılacak dizi olur ve bu sayede arama yapılan listedeki eleman sayısı her adımda yarıya indirilmiş olur.

Uygulama

Bilmeniz gerekenler

• C programlama struct yapısı
• C programlama strcmp fonksiyonu (iki karakter dizisini karşılaştırır eşit ise 0, birinci ifade büyük ise 1, ikinci ifade büyük ise -1 dönderir)

Aşağıda bulunan kodu inceleyerek bu işlemlerin nasıl yapıldığını anlamaya çalışın gerekli açıklamalar kodun yorum satırında mevcuttur.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
/*
* Şair defterine programcı yorum satırına şiirini yazar
* Umut SİNAV (@umutsinav)
*/
// person isimli struct yapımızı tanımlıyoruz
struct person {
  long telNo;
  char isim[12];
};
//İkili (binary) arama algoritmasının özdevingen (recursive) sürümü
int ikiliAramaRecursive(struct person personel[], char arananIsim[], int elemanSayisi, int alt, int ust)
{
	int konum=-1, orta, karsilastir;
	if(alt>ust) return -1;
	//orta kısmı buluyoruz
	orta =  (alt + ust)  /  2;
	//isimleri karşılaştırıyoruz strcmp fonksiyonu ile
	karsilastir = strcmp(arananIsim, personel[orta].isim);
	//karşılaştırma işleminden dönen değere göre return işlemimizi yapıyoruz
	if (karsilastir==0)	return orta;
	else if (karsilastir==-1) return ikiliAramaRecursive(personel, arananIsim,  elemanSayisi, alt, orta-1);
	else if(karsilastir==1) return ikiliAramaRecursive(personel, arananIsim,  elemanSayisi, orta+1, ust);
	//aranan kayit bulunamadı ise -1 değerini dönderiyoruz
	return -1;
}
void main()
{
	struct person
    personel[15]={
		3451280, "AYDIN",
			3892345,"BEKIR",
			3774860,"CEMIL",
			3886655,"DENIZ",
            3871288,"EREN",
			3661288,"EMRAH",
            3661090,"FIKRET",
			3213045,"GUL",
			3871280,"JALE",
			3223488,"LATIF",
			3981200,"NERMIN",
            3021288,"PERIHAN",
            3891123,"UMUT",
			3125466,"VELI",
			3014560,"ZEKI"
	};
	char  girilenIsim[12];
	int elemanSayisi=15, alt=0, ust=15, sonuc, devam=0;
	//elemanları listeliyoruz
	for(int i=0; i<elemanSayisi; i++)
		printf("\n\t %d %s", personel[i].telNo, personel[i].isim);
	do
	{
		//arama yapılacak ismi kullanıcıdan alıyoruz
		printf("\n\tListede Arama Yapmak Icin Kisinin Adini Giriniz:");
		scanf("%s", &girilenIsim);
		//fonksiyonumuzu çağırıyoruz
		sonuc=ikiliAramaRecursive(personel, girilenIsim, elemanSayisi, alt, ust);
		if(sonuc==-1)
			printf("\n\t uzgunuz istediginiz ismi bulamadik :)\n");
		else
			printf("\n\t Aranan ismin konumu: %d\n\t Aranan ismin numarasi: %d\n", sonuc+1, personel[sonuc].telNo);
		printf("Tekrar arama icin [1], cikmak icin [0]:");
		scanf("%d", &devam);
		if(devam==0) exit(0);
	}while(devam);

}