STL - Ricerca binaria

Dal quinto capitolo di Designing Components with the C++ STL, di Ulrich Breymann. Algoritmi standard.

Sezione dedicata agli algoritmi di ordinamento, merging e operazioni correlate. Tutti gl algoritmi di questa sezione hanno due varianti. Una che usa l'operatore '<' per confrontare gli elementi, l'altra che usa una funzione o un functor chiamato comp.

5.5.3: binary_search, lower_bound, upper_bound, equal_range

Questi algoritmi lavorano su una sequenza che é supposta ordinata in ordine crescente, o con lo stesso ordine specificato dal comparatore che passiamo alla funzione.

Con binary_search controlliamo se esiste un elemento nella sequenza passata che per cui valga la relazione (!(*i < value) && !(value < *i).

L'iteratore tornato da lower_bound punta alla prima posizione in cui possiamo inserire nella sequenza un valore senza alterarne l'ordinamento.

L'iteratore tornato da upper_bound punta all'ultima posizione in cui possiamo inserire nella sequenza un valore senza alterarne l'ordinamento.

La coppia di iteratori tornata da equal_range delimita l'intervallo in cui é possibile inserire il valore senza alterare l'ordinamento della sequenza.

Ecco un esempio:

#include<iostream>
#include<algorithm>
#include<list>
#include<string>

using namespace std;

void dump(const list<string>& v) {
    list<string>::const_iterator it = v.begin();
    while (it != v.end()) {
        cout << *it++ << ' ';
    }
    cout << endl;
}

int main() {
    list<string> places;
    places.push_front("Bremen");
    places.push_front("Paris");
    places.push_front("Milan");
    places.push_front("Hamburg");
    places.sort(); // important precondition!
    dump(places);

    string city("Tokio");
    if (binary_search(places.begin(), places.end(), city) == false)
        cout << city << " does not exist in the list" << endl;

    city = "Milan";
    if (binary_search(places.begin(), places.end(), city))
        cout << city << " is already in the list" << endl;

    cout << "Duplicating " << city << " in the list ..." << endl;
    list<string>::iterator it = lower_bound(places.begin(), places.end(), city);
    places.insert(it, city);
    dump(places);

    // range of identical values
    pair<list<string>::const_iterator, list<string>::const_iterator> p =
            equal_range(places.begin(), places.end(), city);

    // The two iterators of the pair p limit the range in which City occurs:
    list<string>::difference_type n = distance(p.first, p.second);
    cout << city << " is contained " << n << " times in the list" << endl;
}

Inizializziamo la lista, la ordiniamo, verifichiamo con una prima chiamata a binary_search() che Tokio non sia nella lista, e con una seconda vediamo che Milan invece c'é. Con lower_bound() troviamo la prima posizione in cui é possibile inserire Milan mantenendo l'ordine nella lista. Con equal_range() troviamo gli iteratori all'inizio e alla fine del subintervallo contenente gli elementi "Milan", con distance() ne troviamo il numero.