lower_bound i upper_bound u C++

Lekcija 2 od 4 · Binarna pretraga

Biblioteka <algorithm> ima gotove funkcije za binarnu pretragu. Sa njima se u jednom redu nalazi prvo pojavljivanje, broj pojavljivanja, broj elemenata u intervalu ili najbliži element – bez grešaka sa granicama.

Pre nego što počneš: potrebno predznanje – binarna pretraga, funkcija sort.
Kako da učiš: svaki primer prekucaj i pokreni, a zadatke na kraju prvo reši sam/a; uputstvo i rešenje otvori tek posle toga. Svi programi su u C++-u.

Tri funkcije

Za sortiran niz (ili vektor) i vrednost x:

Funkcija	Vraća	Primer: a = 1 3 3 3 7 9, x = 3
`lower_bound(b, e, x)`	prvi element >= x	pozicija 1
`upper_bound(b, e, x)`	prvi element > x	pozicija 4
`binary_search(b, e, x)`	`true` ako x postoji	true

lower_bound i upper_bound vraćaju iterator (pokazivač na element). Poziciju dobijamo oduzimanjem početka: lower_bound(v.begin(), v.end(), x) - v.begin(). Ako takvog elementa nema, vraćaju end(), tj. poziciju n.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    vector<int> a = {1, 3, 3, 3, 7, 9};
    int x = 3;
    int lb = lower_bound(a.begin(), a.end(), x) - a.begin();
    int ub = upper_bound(a.begin(), a.end(), x) - a.begin();
    cout << "prvi >= 3 na poziciji " << lb << endl;
    cout << "prvi > 3 na poziciji " << ub << endl;
    cout << "broj trojki: " << ub - lb << endl;
    cout << "ima li 5? " << (binary_search(a.begin(), a.end(), 5) ? "da" : "ne") << endl;
    cout << "lower_bound za 10: " << lower_bound(a.begin(), a.end(), 10) - a.begin() << endl;
    return 0;
}

Tipični upiti

Pitanje	Izraz (niz sortiran rastuće)
Koliko elemenata je < x?	`lower_bound(..., x) - a.begin()`
Koliko elemenata je <= x?	`upper_bound(..., x) - a.begin()`
Koliko puta se javlja x?	`upper_bound(..., x) - lower_bound(..., x)`
Koliko elemenata je u [L, R]?	`upper_bound(..., R) - lower_bound(..., L)`
Koliko elemenata je >= x?	`a.end() - lower_bound(..., x)`

Za običan niz umesto a.begin() i a.end() pišemo a i a + n.

Primer: najbliži element

Za svaki upit x tražimo element niza najbliži broju x. Kandidati su prvi element >= x (pozicija p) i element pre njega (pozicija p − 1) – sve ostalo je dalje.

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdlib>
using namespace std;

int main() {
    int n, q;
    cin >> n;
    vector<int> a(n);
    for (int &v : a) cin >> v;
    sort(a.begin(), a.end());
    cin >> q;
    while (q--) {
        int x;
        cin >> x;
        int p = lower_bound(a.begin(), a.end(), x) - a.begin();
        int naj = -1;
        if (p < n) naj = a[p];                                     // prvi >= x
        if (p > 0 && (naj == -1 || x - a[p - 1] <= naj - x)) naj = a[p - 1];  // prethodni (kod jednake udaljenosti manji)
        cout << naj << "\n";
    }
    return 0;
}

Napomene

Niz mora biti sortiran istim poretkom koji funkcija očekuje (podrazumevano rastuće). Za opadajuće sortiran niz koristi se lower_bound(b, e, x, greater<int>()).
Radi i nad vektorom parova i stringova: lower_bound(v.begin(), v.end(), make_pair(x, -1)).
Kontejneri set i map imaju sopstvene metode s.lower_bound(x) – one su brze, dok je lower_bound(s.begin(), s.end(), x) nad skupom spora (O(n)).

Zadaci za vežbu

Za svaki zadatak postoji primer, uputstvo i rešenje. Rešenja su provereno tačna na primerima iz teksta.

ZADATAK 01Težina: Lako

Brojevi u intervalu

Dato je n brojeva i q upita oblika L R (1 ≤ n, q ≤ 10⁵). Za svaki upit ispiši koliko brojeva je u intervalu [L, R].

Primer

Ulaz

6
5 1 9 3 3 7
3
3 7
10 20
1 9

Izlaz

4
0
6

Rešenje (C++)

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, q;
    cin >> n;
    vector<int> a(n);
    for (int &v : a) cin >> v;
    sort(a.begin(), a.end());
    cin >> q;
    while (q--) {
        int L, R;
        cin >> L >> R;
        cout << upper_bound(a.begin(), a.end(), R) - lower_bound(a.begin(), a.end(), L) << "\n";
    }
    return 0;
}

ZADATAK 02Težina: Srednje

Parovi sa zbirom najviše S

Dato je n brojeva (1 ≤ n ≤ 10⁵) i broj S. Koliko ima parova pozicija i < j za koje je a[i] + a[j] <= S?

Primer

Ulaz

5 10
2 7 5 3 9

Izlaz

Rešenje (C++)

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int n;
    long long S;
    cin >> n >> S;
    vector<long long> a(n);
    for (auto &v : a) cin >> v;
    sort(a.begin(), a.end());
    long long br = 0;
    for (int i = 0; i < n; i++) {
        auto poc = a.begin() + i + 1;                       // partner je iza i
        br += upper_bound(poc, a.end(), S - a[i]) - poc;    // koliko je <= S - a[i]
    }
    cout << br << endl;
    return 0;
}

Česte greške i saveti

Niz mora biti sortiran pre poziva.
Rezultat je iterator; poziciju dobijaš oduzimanjem a.begin().
Pre čitanja a[p] proveri da je p < n – ako traženog elementa nema, p je n.

Proveri znanje

Otvori kviz