Informatică Programare
Cautare binara algoritm C++
Căutarea binară este un algoritm eficient care găsește un element într-un vector sortat, reducând spațiul de căutare la jumătate la fiecare pas. În C++, se implementează cu o buclă while sau recursivitate.
Condiții necesare
- Vector sortat Elementele trebuie să fie aranjate în ordine crescătoare sau descrescătoare.
- Acces aleator Trebuie să poți accesa orice element direct, ca într-un vector.
Pași algoritm
- 1 Pasul 1: Inițializează limitele Set left=0 și right=n-1, unde n este numărul de elemente.
- 2 Pasul 2: Calculează mijlocul mid = left + (right-left)/2 pentru a evita overflow.
- 3 Pasul 3: Compară cu elementul căutat Dacă arr[mid]==x, returnează mid. Dacă arr[mid]<x, left=mid+1, altfel right=mid-1.
- 4 Pasul 4: Repetă până la găsire sau epuizare Continuă până când left>right, caz în care elementul nu există.
Exemplu cod
- Implementare iterativă int binarySearch(int arr[], int n, int x) { int left=0, right=n-1; while(left<=right) { int mid=left+(right-left)/2; if(arr[mid]==x) return mid; else if(arr[mid]<x) left=mid+1; else right=mid-1; } return -1; }
- Complexitate O(log n), mult mai rapid decât căutarea liniară O(n) pentru vectori mari.
Verifică mereu dacă vectorul este sortat înainte de a aplica căutarea binară.