[Algoritmi si Tehnici de Programare - C] Algoritmul de Cautare Binar (In Stil Recursiv)

[Soulrayne]

OBIECTIV

 

VOM PROIECTA (PRIN DIAGRAMA UML) , IMPLEMENTA (COD C) SI TESTA ALGORITMUL DE CAUTARE BINARA IN STIL RECURSIV SI GENERIC !! 

PROIECTARE 

 

AICI AVEM O PROIECTARE A ALGORITMULUI DE CAUTARE BINARA IN LIMBAJUL UML (Modelare).

 

 

NOTA : SUNT INCEPATOR IN UML , PRIN URMARE SE POT VEDEA ANUMITE GRESELI DE ASEZARE A ACTIUNILOR DAR IDEEA E ACEEASI  ! 

 

IMPLEMENTARE IN C

 

NOTA : Sa presupunem ca avem un SIR SORTAT . ESTE INEFICIENT DACA NU E SORTAT !! 

ANTENTUL FUNCTIEI VA ARAT , OARECUM , SIMILAR CU CEL DE LA TUTORIALUL TRECUT (TOTUSI , APAR MICI DIFERENTE PE CARE LE VOM NOTA ) 

 

int binary_search_recursive(void* a,size_t elementSize,int lowIndex , int highIndex,void* searchedElement,int (*genericCMP)(const void*,const void*)) 
{
// CODUL CE VA FI SCRIS
}

 

♦ pointerul "a" reprezinta colectia de numere preluata de la tastatura ;

♦ "elementSize" reprezinta numarul de biti stocata de tipul de date pe care dorim sa l prelucram ;

♦ "lowIndex" reprezinta indexul inferior (Limita din  Stanga) ;     Cum ar venii  [3,7]   ==>  0 (3)

♦ "highIndex" reprezinta indexul superior (Limita din Dreapta) ;  Cum ar venii [3,7]  ==> N-1 (7) ==> Unde "N" reprezinta numarul total de elemente ; 

♦ "searchedElement" reprezinta elementul cautat ; 

♦ "generic" reprezinta interfata generic de comparare a elementelor . Practic , e o functie generica care pointeaza catre o functie de comparare potrivita pentru tipul de date prezent . 

 

Revenim , prima data , ne intereseaza daca mai avem elemente de comparat . Astfel , va trebui sa comparam limita inferioara cu superioara . 

 

// 1. VERIFICAM DACA MAI EXISTA ELEMENTE (FARA ASTA DUCEM ALGORITMUL IN STACKOVERFLOW !!  

if(lowIndex > highIndex)

 

Daca se indeplineste conditia , ne da de inteles ca nu am gasit elementul,  desi , am traversat intervalele "targetate" . Prin urmare , oprim algoritmul pentru a evita "stackoverflow" (supraincarcarea memoriei stack la infinit). 

 

return -1; // NU AM GASIT ELEMENTUL

 

Mai departe , daca avem de verificat , vom afla mijlocul dintre cele doua extreme . 

 

// 2. AFLAM MEDIA DINTRE CELE DOUA EXTREME 

int mid = (lowIndex + highIndex)/2;

 

Comparam elementul din mijloc cu cel cautat 

 

// 3. COMPARAM ELEMENTUL DIN MIJLOCUL INTERVALULUI FORMAT DINTRE CELE DOUA EXTREME        

int result = genericCMP((char*)a+mid*elementSize,searchedElement); // TRIMITEM ADRESELE PENTRU COMPARATIA VALORILOR ASOCIATE ACESTORA

 

Pentru acest algoritm , vom schimba putin interfata de comparatie a numerelor : 

 

int compareInt(const void* a,const void* b) // FUNCTIE PENTRU COMPARAREA INTREGILOR 

{ 

if(*(int*)a == *(int*)b) 
return 1; 

else if((*(int*)a > *(int*)b)) 
return 0; 

else 
return -1; 

}

 

Acum , vom avea 3 rezultate : 

 

→ In cazul in care elementele sunt egale (avem 1) , am gasit elementul cautat si vom returna indexul asociat acestuia : 

 

if(result == 1) // SUNT EGALE 
return mid; // AM GASIT ELEMENTUL SI TRIMITEM INDEXUL ASOCIAT VALORI

 

→ In cazul in care elementul cautat este mai mic decat mijlocul (avem 0) , vom cauta spre partea inferioara (stanga) : 

 

else if(result == 0) // DACA ELEMENTUL ACTUAL ESTE MAI MARE DECAT CEL CAUTAT 
return binary_search_recursive(a,elementSize,lowIndex,mid,searchedElement,genericCMP); // VOM RETURNA RECURSIV FUNCTIA FORMAND ALT INTERVAL MAI MIC CU INDEXUL INFERIOR SI MIJLOCUL

 

→ In cazul in care elementul cautat este mai mare decat mijlocul (avem -1) , vom cauta spre partea superioara (dreapta) : 

 

else 
return binary_search_recursive(a,elementSize,mid,highIndex,searchedElement,genericCMP); // VOM RETURNA RECURSIV FUNCTIA FORMAND ALT INTERVAL MAI MIC CU INDEXUL DIN MIJLOC SI INDEXUL SUPERIOR

 

Pe scurt , subprogramul cu algoritmul de cautare , va arat in felul urmator : 

 

int binary_search_recursive(void* a,size_t elementSize,int lowIndex , int highIndex,void* searchedElement,int (*genericCMP)(const void*,const void*)) //RETURNAM INDEXUL ELEMENTULUI CAUTAT 
{ 

// 1. VERIFICAM DACA MAI EXISTA ELEMENTE (FARA ASTA DUCEM ALGORITMUL IN STACKOVERFLOW !! ) 
if(lowIndex > highIndex) 
return -1; // NU AM GASIT ELEMENTUL 

// 2. AFLAM MEDIA DINTRE CELE DOUA EXTREME 
int mid = (lowIndex + highIndex)/2; 

// 3. COMPARAM ELEMENTUL DIN MIJLOCUL INTERVALULUI FORMAT DINTRE CELE DOUA EXTREME 
int result = genericCMP((char*)a+mid*elementSize,searchedElement); // TRIMITEM ADRESELE PENTRU COMPARATIA VALORILOR ASOCIATE ACESTORA 

if(result == 1) // SUNT EGALE 
return mid; // AM GASIT ELEMENTUL SI TRIMITEM INDEXUL ASOCIAT VALORI 

// 4. DACA NU L-AM GASIT 
else if(result == 0) // DACA ELEMENTUL ACTUAL ESTE MAI MARE DECAT CEL CAUTAT 
return binary_search_recursive(a,elementSize,lowIndex,mid,searchedElement,genericCMP); 

else 
return binary_search_recursive(a,elementSize,mid,highIndex,searchedElement,genericCMP); 

}

 

TESTARE

 

Dupa implementare , vom testa in programul principal codul : 

 

int main() 
{ 
int* a = (int*)malloc(sizeof(int)); // Declaram o colectie cu un element 
int bufferArr = insertArray(&a);// Trimitem pointerul a prin adresa (VOM MODIFICA STRUCTRURA ACESTUIA IN FUNCTIE ) si 
// ++ Vom returna lungimea finala in bufferArr 

int searchedNumber, searchedIndex; 

printf("\nINTRODUCETI NUMARUL CAUTAT : "); 
scanf("%d",&searchedNumber); 

// APELAM FUNCTIA DE CAUTARE LINIARA 
; 
if((searchedIndex = binary_search_recursive(a,sizeof(int),0,bufferArr-1,&searchedNumber,compareInt)) != -1) 
printf("AM GASIT ELEMENTUL CAUTAT LA INDEXUL %d !!",searchedIndex); 
else 
printf("NU AM GASIT ELEMENTUL IN COLECTIE !! \n"); 

free(a); // Eliberam Colectia in Sine 
a = NULL; // Setam NULL Pointer 

}

 

Dupa o simpla executie , vom avea : 

 

Edited February 5 by Soulrayne