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 **
Cod: Selectaţi tot
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 !! Cod: Selectaţi tot
#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;
}Cod: Selectaţi tot
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 
