Articole

Standard Template Library – STL conține două funcții extrem de utile care realizează căutarea binară, lower_bound și upper_bound. Ele se găsesc în headerul algorithm și realizează căutarea atât pentru vectori STL cât și pentru tablourile unidimensionale standard C. În ambele cazuri elementele structurii de date trebuie să fie ordonate după un anumit criteriu, iar funcțiile au următoarele rezultate:

lower_bound – cel mai din stânga element care este mai mare sau egal cu valoarea căutată;
upper_bound – cel mai din stânga element care este strict mai mare decât valoarea căutată.

Observație: STL conține și funcția binary_search, care caută într-o structură de date o anumită valoare și returnează true dacă o găsește și false în caz contrar. Funcția lower_bound furnizează informații suplimentare, fiind astfel mai utilă în practică.

Căutarea în vectori STL

Antetele funcțiilor sunt:

Iterator lower_bound(Iterator p, Iterator u, Valoare v);
Iterator lower_bound(Iterator p, Iterator u, Valoare v, Comparator fcmp);

Valoare este un tip de date oarecare pentru care este definită relația de ordine < sau funcția comparator fcmp, iar p și u sunt iteratori la elemente ale unui vector STL de tip vector<Valoare>.

Funcția caută în secvența [p,u) cel mai din sțânga element mai mare sau egal cu v și returnează iterator la acel element, sau u, dacă nu există un asemenea element nu există. Dacă elementele vectorului sunt ordonate după un alt criteriu decât <, se folosește o funcție de comparare fcmp.

Iterator upper_bound(Iterator p, Iterator u, Valoare v);
Iterator upper_bound(Iterator p, Iterator u, Valoare v, Comparator fcmp);

Funcția caută în secvența [p,u) cel mai din sțânga element mai mare strict decât v și returnează iterator la acel element, sau u, dacă nu există un asemenea element nu există. Dacă elementele vectorului sunt ordonate după un alt criteriu decât <, se folosește o funcție de comparare fcmp.

În funcțiile de mai sus, numele parametrilor au următoarea semnificație:

p – primul
u – ultimul
v – valoarea de căutat
f – comparator (funcție de comparare)

Important: Elementul u nu face parte din secvența în care se caută valoarea v.

Exemplu

vector<int> A;
int k;
....
auto I = lower_bound(A.begin(), A.end(), k); // I este iterator
if(I == A.end() || *I != k)
    cout << k << " nu apare în vector";
else
    cout << k << " apare în vector pe poziția " << I - A;

Căutarea în tablouri unidimensionale standard C

Antetele funcțiilor sunt:

Valoare * lower_bound(Valoare * p, Valoare * u, Valoare v);
Valoare * lower_bound(Valoare * p, Valoare * u, Valoare v, Comparator fcmp);

Valoare este un tip de date oarecare pentru care este definită relația de ordine < sau funcția comparator fcmp, iar p și u sunt pointeri la Valoare șî reprezintă adresele unor elemente ale unui tablou declarat Valoare A[dim];.

Funcția caută în secvența [p,u) cel mai din sțânga element mai mare sau egal cu v și returnează pointer la acel element, sau u, dacă nu există un asemenea element nu există. Dacă elementele vectorului sunt ordonate după un alt criteriu decât <, se folosește o funcție de comparare fcmp.

Iterator upper_bound(Iterator p, Iterator u, Valoare v);
Iterator upper_bound(Iterator p, Iterator u, Valoare v, Comparator fcmp);

Funcția caută în secvența [p,u) cel mai din sțânga element mai mare strict decât v și returnează pointer la acel element, sau u, dacă nu există un asemenea element nu există. Dacă elementele vectorului sunt ordonate după un alt criteriu decât <, se folosește o funcție de comparare fcmp.

Exemplu 1

#include <iostream>
#include <algorithm>

int main()
{
    int n = 10, v[]={10, 20, 30, 40, 50, 60, 70, 80, 90, 100}; // indexare de la zero

    //lower_bound: cel mai din stânga iterator i pentru care v[i] >= x
    std::cout << std::lower_bound(v , v + n , 20) - v << std::endl; // 1, v[1] >= 20
    std::cout << std::lower_bound(v , v + n , 25) - v << std::endl; // 2, v[2] >= 25

    //upper_bound: cel mai din stânga iterator i pentru care v[i] > x

    std::cout << std::upper_bound(v , v + n , 20) - v << std::endl; // 2, v[2] > 20
    std::cout << std::upper_bound(v , v + n , 25) - v << std::endl; // 2, v[2] > 25

    return 0;
}

Exemplu 2

int A[1000], n; // indexat de la  0  la n - 1
int k;
....
int * q = lower_bound(A, A + n, k); // q este pointer
    if(q == A + n || *q != k)
        cout << k << " nu apare în tablou";
    else
        cout << k << " apare în tablou la indicele " << q - A;

Funcția de comparare

Dacă elementele vectorului (tabloului) satisfac altă relație de ordine, va trebui să definim o funcție de comparare, fcmp, sau să folosim un predicat din STL. De exemplu, dacă vectorul (tabloul) are elementele în ordine descrescătoare putem folosi greater. De exemplu:

int A[1000], n; // indexat de la  0  la n - 1
int k;
....
int * q = lower_bound(A, A + n, k, greater<int>());

În cazul unei relații de ordine mai complexe, se poate defini o funcție de comparare, în felul următor:

bool fcmp(Valoare A, Valoare B);

Funcția are doi parametru de același tip cu elementel tabloului (vectorului) în care face căutarea și va returna true, dacă primul parametru, A, este strict înaintea lui B în ordinea dorită și false în caz contrar.

Referințe

Citește articolul

2021-04-23 |

Căutarea binară

Introducere

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ăutării 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).

Algoritm pseudocod

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

DACĂ poz≠0 ATUNCI
    // x apare în vector pe poziția poz
ALTFEL
    // x nu apare în vector 
SFDACĂ

Notă: În algoritmul de mai sus a DIV b reprezintă câtul împărțirii lui a la b, iar cu V ← EXPR s-a notat atribuirea la variabila V a rezultatului expresiei EXPR.

Altă variantă a căutării binare

De multe ori nu este suficient să știm dacă o valoare dată apare sau nu în vector. Sunt numeroase situații în care trebuie să aflăm un indice al vectorului (element al vectorului) care respectă o anumită condiție în raport cu valoarea dată. De exemplu:

să se determine cel mai mare indice poz pentru care v[poz] ≤ x;
să se determine cel mai mare indice poz pentru care v[poz] < x;
etc.

Algoritmul de mai jos determină cel mai mare indice poz pentru care v[poz] ≤ x. El poate fi folosit și pentru a verifica dacă x apare în vector, astfel: dacă la final v[poz] = x, atunci x apare în vector, in caz contrar nu apare.

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

DACĂ v[poz] = x ATUNCI
    // x apare în șir pe poziția poz
ALTFEL
    // x nu apare în șir (în acest caz, v[poz] > x)
SFDACĂ