std::lower_bound în C++

ForwardIt lower_bound(ForwardIt first, ForwardIt last, const T& valoare);
ForwardIt upper_bound(ForwardIt first, ForwardIt last, const T& valoare);

Ce face std::lower_bound

Ambele folosesc căutarea binară, deci intervalul trebuie să fie sortat. std::lower_bound returnează prima poziție unde ai putea insera valoarea fără să strici ordinea: primul element care nu este mai mic decât ea. std::upper_bound returnează primul element strict mai mare.

Diferența upper_bound - lower_bound este numărul de apariții ale valorii. Dacă valoarea este mai mare decât toate elementele, ambele returnează last.

Parametri

Parametru	Descriere
first, last	Interval sortat.
valoare	Valoarea de referință.
comp	Opțional (al patrulea argument). Criteriul de sortare folosit.

Ce returnează

Un iterator în interval (sau last).

Exemple

Exemplul 1: Unde se află valoarea 5

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

int main() {
    std::vector<int> v{1, 3, 5, 5, 5, 8, 9};

    auto jos = std::lower_bound(v.begin(), v.end(), 5);
    auto sus = std::upper_bound(v.begin(), v.end(), 5);

    std::println("lower_bound: poziția {}", jos - v.begin());
    std::println("upper_bound: poziția {}", sus - v.begin());
    std::println("5 apare de {} ori", sus - jos);
}

Rezultat

lower_bound: poziția 2
upper_bound: poziția 5
5 apare de 3 ori

Exemplul 2: Inserare păstrând vectorul sortat

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

int main() {
    std::vector<int> scoruri{10, 25, 40, 70};

    for (int nou : {30, 5, 90}) {
        scoruri.insert(std::ranges::lower_bound(scoruri, nou), nou);
    }
    std::println("{}", scoruri);
}

Rezultat

[5, 10, 25, 30, 40, 70, 90]

Exemplul 3: Tarif după greutatea coletului

Pragurile sunt sortate; lower_bound găsește primul prag care acoperă greutatea.

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

int main() {
    std::vector<double> praguri_kg{1, 5, 10, 20};
    std::vector<int> tarife_lei{15, 22, 30, 45};

    for (double kg : {0.5, 5.0, 7.3, 25.0}) {
        auto it = std::lower_bound(praguri_kg.begin(), praguri_kg.end(), kg);
        if (it == praguri_kg.end()) {
            std::println("{} kg: prea greu", kg);
        } else {
            std::println("{} kg: {} lei", kg, tarife_lei[it - praguri_kg.begin()]);
        }
    }
}

Rezultat

0.5 kg: 15 lei
5 kg: 22 lei
7.3 kg: 30 lei
25 kg: prea greu

Greșeli frecvente

• Dereferențiezi rezultatul fără să verifici dacă este end(), pentru o valoare mai mare decât toate.
• Crezi că lower_bound confirmă existența valorii. Verifică și *it == valoare.

Comenzi înrudite

• std::binary_search: Verifică foarte rapid dacă o valoare există într-un interval deja sortat.
• std::equal_range: Într-un interval sortat, returnează perechea de iteratori care delimitează toate elementele egale cu valoarea.
• std::sort: Sortează elementele dintr-un interval, crescător sau după o regulă dată de tine.