Căutarea binară


Editat de Candale Silviu (silviu) la data 2018-02-07

Căutarea unei valori într-un vector se poate face în două moduri:

  • secvențial – presupune analizarea fiecărui element al vectorului într-o anumită ordine (de obicei de la stânga la dreapta). Când se găsește valoarea căutată parcurgerea vectorului se poate opri. În cel mai rău caz, pentru un vector cu n elemente parcurgerea face n pași, complexitatea timp a căutarii secvențiale este O(n)
  • binar. Căutarea binară se poate face într-un vector numai dacă elementele acestuia sunt în ordine (de obicei crescătoare) după un anumit criteriu (de obicei criteriul este chiar relația de ordine naturală între numere, cuvinte, etc). Căutarea binară presupune împărțirea vectorului în secvențe din ce în ce mai mici, înjumătățindu-le și continuând cu jumătatea în care se poate afla valoarea dorită (conform ordinii elementelor din vector).

Algoritmul căutării binare este următorul:

Date de intrare:

  • un vector v[] cu n elemente, indexate de la 1 la n, ordonate crescător și o valoare x care se va căuta.

Date de ieșire:

  • un indice poz dacă valoarea x apare în vectorul v[] sau 0 în caz contrar.

Algoritm pseudocod:

st ← 1
dr ← n
poz ← 0
CÂTTIMP st < dr SI poz = 0 EXECUTĂ
    m ← (st + dr) DIV 2
    DACĂ v[m] = x ATUNCI 
        poz = m
    ALTFEL
        DACĂ v[m] < x ATUNCI
            st ← m + 1
        ALTFEL
            dr ← m -1
        SFDACĂ
    SFDACĂ
SFCÂTTIMP

În unele situații este important să stabilim pe ce poziție poate fi inserată în vectorul v[] valoarea x astfel încât elementele vectorului să rămână în ordine crescătoare. El poate fi utilizat și pentru verificarea existenței lui x în v[], ca în algoritmul de mai jos.

st ← 1
dr ← n
CÂTTIMP st < dr EXECUTĂ
    m ← (st + dr) DIV 2
    DACĂ v[m] < x ATUNCI 
        st ← m + 1
    ALTFEL
        dr ← m
    SFDACĂ
SFCÂTTIMP
// poziția pe care trebuie inserat x este st
DACĂ v[st] = x ATUNCI
    // x apare în șir pe poziția st
ALTFEL
    // x nu apare în șir (în acest caz, v[st] > x)
SFDACĂ

Fișiere atașate


Probleme ataşate

Nr. Problema Clasa Dificultate Operații I/O
1 #0508 - Cautare Binara 9 medie consola
2 #0661 - Triunghiuri1 9 dificilă consola
Editat de Candale Silviu (silviu) la data 2018-02-07