Căutarea secvențială și căutarea binară

Căutarea secvențială

Parcurgi vectorul de la început până găsești elementul sau ajungi la capăt.

• Complexitate: $O(n)$.
• Avantaj: funcționează pe orice vector, sortat sau nu.

Căutarea binară

Condiție obligatorie: vectorul trebuie să fie SORTAT. Pe un vector nesortat dă rezultate greșite, nu eroare, ceea ce e mai periculos.

Ideea: compari cu elementul din mijloc și elimini jumătate din intervalul de căutare la fiecare pas.

1. st = 0, dr = n - 1;
2. cât timp st <= dr:
   • mij = (st + dr) / 2;
   • dacă v[mij] == x, ai găsit;
   • dacă v[mij] < x, cauți în dreapta: st = mij + 1;
   • altfel cauți în stânga: dr = mij - 1;
3. dacă bucla se termină, elementul nu există.

Complexitate: $O(\log n)$. Pentru un milion de elemente, cel mult 20 de pași.

Capcana depășirii

mij = (st + dr) / 2 poate depăși tipul întreg când st și dr sunt mari, pentru că suma lor depășește limita înainte de împărțire.

Varianta sigură: $mij = st + \frac{dr - st}{2}$

Matematic e același lucru, dar nu trece niciodată prin suma mare. E un bug celebru, care a stat ascuns ani de zile în biblioteci standard.

Comparație

Greșeli frecvente

1. Se aplică binară pe vector nesortat. Rezultatul e greșit, dar programul nu dă eroare.
2. Se scrie st = mij în loc de st = mij + 1, și bucla nu se mai termină.
3. Se folosește st < dr în loc de st <= dr, și se ratează elementul când intervalul are un singur element.

#include <iostream>
using namespace std;

int main() {
    int n, x, v[100];
    cin >> n >> x;
    for (int i = 0; i < n; i++) cin >> v[i];

    int st = 0, dr = n - 1, gasit = -1, pasi = 0;
    while (st <= dr) {
        pasi++;
        int mij = st + (dr - st) / 2;
        if (v[mij] == x) { gasit = mij; break; }
        if (v[mij] < x) st = mij + 1;
        else dr = mij - 1;
    }

    if (gasit >= 0) cout << "gasit pe pozitia " << gasit << " in " << pasi << " pasi";
    else cout << "negasit in " << pasi << " pasi";
    return 0;
}