binary search [Algoritmi si Tehnici de Programare] Cautare Binara

[King Of Underground]

** Algoritm de Cautare Binar ** 

Este un algoritm de cautare utilizat intr-o colectie  SORTATA ,  ne ofera posibilitatea de a miscora timpul de executie (Complexitate Timp mai optim) prin divizarea repetata a intervalelor la jumatate .   

** Explicatie ** 

Sa presupunem ca avem o colectie de 10 numere (SORTATA) : 

      [11 , 22 , 34 , 56 , 65 , 76 , 78 , 84 , 96 , 98]
      
      
    Si dorim sa aflam daca exista numar 78 in colectie si la ce index : 
    
    APLICAM ALGORITMUL :: 
    
    --> AFLAM INDEX-UL CARE-I CORESPUNDE NUMARULUI DIN MIJLOCUL INTERVALULUI : (9+0)/2 = 4.5 ==> 5 
         ==> Verificam daca a[5] = 76 este echivalent cu 78 ==> DIFERIT CONTINUAM ALGORITMUL ;  
 
    --> CUNOASTEM FAPTUL CA 78 > 76 ASA CA VOM STII CA NUMARUL CAUTAT SE AFLA IN INTERVALUL DIN DREAPTA  

         [76 , 78 , 84 , 96 , 98 ]
        --> AFLAM INDEXUL CAREI CORESPUNDE NUMARUL DIN MIJLOCUL INTERVALULUI : (5+9)/2 = 14/2 = 7 (indexul din mijloc)
             ==> Verificam daca a[7] = 84 este echivalent cu 78 ==> DIFERIT CONTINUAM ALGORITMUL ; 
             
    --> CUNOASTEM FAPTUL CA 84 > 78 ASA CA VOM STII CA NUMARUL CAUTAT SE AFLA IN INTERVALUL DIN STANGA 
         [ 76 , 78 , 84 ]
          --> AFLAM INDEXUL CAREI CORESPUNDE NUMARUL DIN MIJLOCUL INTERVALULUI : (5+7)/2 = 6 (Indexul din mijloc)
              ==> verficam daca [a6] = 78 = este echivalent cu 78 ==> AM GASIT ELEMENTU , INTRERUPEM ALGORITMUL CU SUCCES !! 
       

** Interpretare in Cod C ** : 

#include <stdio.h>
#include <stdlib.h> // Pentru malloc & free


int main()
{
	int arrayBuffer;

	printf("Cate numere doresti sa aiba colectia : ");
	
	scanf_s("%d", &arrayBuffer);

	int* a = (int*)malloc(arrayBuffer * sizeof(int)); // ALOCAM UN ARRAY IN FUNCTIE DE CATE NUMERE VREA UTILIZATORUL SA INTRODUCA
	
	printf("Insereaza %d numere in sir crescator : \n",arrayBuffer);


		for (int i = 0; i < arrayBuffer; i++)
		{
			printf("colectie[%d] = ",i);
			scanf_s("%d", &a[i]);  // Inseram numerele de la tastatura 
		
		}

		int numberToSearch, found = 0, index;

		do {
			printf("Insereaza numarul pe care vrei sa l cauti in colectie : ");
			scanf_s("%d", &numberToSearch);

			
			int leftIndex = 0, RightIndex = arrayBuffer - 1; // Aflam Primul Si Ultimul Index 

			// LE AM INITIALIZAT IN AFARA LOOPULUI PENTRU A SI PASTRA VALOAREA LA FIECARE ITERARE !!! 

			do {
				int mid = (leftIndex + RightIndex) / 2; // Aflam Indexul Din Mijlocul Intervalului  

				if (a[mid] == numberToSearch) // Comparam Cu Mijlocul 
				{
					// Daca Am gasit numarul 
					index = mid;  // Preluam Indexul 
					found = 1;
					break;
				}

				else if(a[mid] < numberToSearch) {  // DACA NUMARUL CAUTAT ESTE MAI MARE DECAT MIJLOCUL 
					leftIndex = mid; // Vom Cauta in Continuare de la Mijloc Spre Dreapta
				}

				else {   // DACA NUMARUL CAUTAT ESTE MAI MIC DECAT MIJLOCUL 
					RightIndex = mid;
				}

			} while (leftIndex <= RightIndex);

			printf("\n");

		} while (found == 0);


		printf("Am gasit elementul %d la pozitia %d", numberToSearch, index); 


		// Eliberam Memoria Ocupata de Array (Sa prevenim Memory Leak)

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


	return 0;
}

NOTA 1  ** : ALGORITM INEFICIENT IN CAZUL COLECTIILOR DEZORDONATE (NESORTATE) !!! 

Explicatie : 

Sa presupunem ca avem o colectie de 10 numere (NESORTAT) : 

      [98 , 33 , 22 , 11 , 65 , 55 , 44 , 78 , 45 , 99]
      
      
    Si dorim sa aflam daca exista numarul 44 in colectie si la ce index : 
    
   Aplicam Algoritmul : 
   
  1. mid = (0+9)/2 = 4.5 
     a[5] = 55 diferit de 44 ==>  55 > 44 ==> CAUTAM IN INTERVALUL DIN STANGA 
     
     [98 , 33 , 22 , 11 , 65 , 55] NU L GASIM PE 44 IN ACEST INTERVAL !! ==> ALGORITMUL ESUEAZA 

NOTA 2 ** :  FOARTE BUN DACA AVEM O COLECTIE MARE DE DATE , SCUTINDU NE DE A CAUTAT FIECARE ELEMENT !! (CU CONDITIA DE A FI ORDONAT)