`std::binary_search` în C++

Verifică foarte rapid dacă o valoare există într-un interval deja sortat.

Sintaxă

bool binary_search(ForwardIt first, ForwardIt last, const T& valoare);
bool binary_search(ForwardIt first, ForwardIt last, const T& valoare, Compare comp);

Ce face `std::binary_search`

std::binary_search folosește căutarea binară: compară valoarea cu elementul din mijloc și păstrează doar jumătatea în care poate fi. Are nevoie de O(log n) pași, deci găsește un element între un milion în circa 20 de comparații.

Condiția obligatorie: intervalul trebuie să fie sortat după același criteriu. Funcția răspunde doar da/nu; pentru poziție folosește std::lower_bound.

Parametri

Parametru	Descriere
`first, last`	Interval sortat.
`valoare`	Valoarea căutată.
`comp`	Opțional. Același criteriu cu care a fost sortat intervalul.

Ce returnează

true dacă există un element egal cu valoarea.

Exemple

Exemplul 1: Căutare într-o listă sortată de coduri

#include <algorithm>
#include <print>
#include <vector>

int main() {
    std::vector<int> coduri{105, 230, 318, 402, 577, 690};

    for (int cod : {318, 400}) {
        bool exista = std::binary_search(coduri.begin(), coduri.end(), cod);
        std::println("Codul {}: {}", cod, exista ? "există" : "nu există");
    }
}

Rezultat

Codul 318: există
Codul 400: nu există

Exemplul 2: Sortezi o dată, cauți de mai multe ori

#include <algorithm>
#include <print>
#include <string>
#include <vector>

int main() {
    std::vector<std::string> invitati{"Radu", "Ana", "Mihai", "Elena", "Ioana"};
    std::ranges::sort(invitati);

    for (const char* nume : {"Elena", "George"}) {
        std::println("{} este invitat: {}", nume, std::ranges::binary_search(invitati, std::string(nume)));
    }
}