STL lower_bound, upper_bound

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.