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

[NOT a MERCEDES]

** 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 :