Prima și ultima apariție prin căutare binară C++

O căutare binară care se oprește la prima egalitate întâlnită poate găsi orice apariție a valorii. Dacă vrei toate pozițiile ocupate de aceeași valoare într-un vector sortat, caută cele două frontiere ale grupului.

Cerință

Citim 0 ≤ n ≤ 1000, valoarea x și n întregi sortați nedescrescător. Afișăm prima poziție, ultima poziție și numărul de apariții ale lui x. Pozițiile afișate sunt de la 1. Dacă valoarea lipsește, afișăm NU EXISTA. Acceptăm inclusiv vectorul gol.

În 1,3,3,3,8, frontiera primei valori cel puțin 3 este 1, iar prima valoare strict mai mare are indicele 4.Mărește schema ↗

Două frontiere, două comparații

Prima căutare găsește cel mai mic indice cu a[i] ≥ x, sau n dacă nu există. A doua găsește cel mai mic indice cu a[i] > x, sau n. Notăm rezultatele prima și dupa. Elementele egale cu x ocupă intervalul semideschis [prima, dupa), deci sunt dupa-prima.

Pentru 1 3 3 3 8 și x=3, frontierele sunt 1 și 4 în indexarea de la zero. Prima poziție afișată este 2, ultima este 4, iar numărul este 3. Ultima poziție de la 1 coincide numeric cu frontiera exclusivă de la zero, dar reprezintă altceva.

Varianta cu tablou clasic

#include <iostream>
using namespace std;
int main() {
    int n, x; cin >> n >> x;
    int a[1000];
    for (int i = 0; i < n; ++i) cin >> a[i];
    int st = 0, dr = n;
    while (st < dr) {
        int m = st + (dr-st)/2;
        if (a[m] < x) st = m+1; else dr = m;
    }
    int prima = st;
    st = 0; dr = n;
    while (st < dr) {
        int m = st + (dr-st)/2;
        if (a[m] <= x) st = m+1; else dr = m;
    }
    int dupa = st;
    if (prima == dupa) cout << "NU EXISTA\n";
    else cout << prima+1 << ' ' << dupa << ' ' << dupa-prima << '\n';
}

Varianta echivalentă cu std::vector

Indicii și datele de intrare rămân aceleași. Containerul este construit cu numărul de elemente folosite; accesul prin [] cere în continuare indici valizi.

#include <iostream>
#include <vector>
using namespace std;
int main() {
    int n, x; cin >> n >> x;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) cin >> a[i];
    int st = 0, dr = n;
    while (st < dr) {
        int m = st + (dr-st)/2;
        if (a[m] < x) st = m+1; else dr = m;
    }
    int prima = st;
    st = 0; dr = n;
    while (st < dr) {
        int m = st + (dr-st)/2;
        if (a[m] <= x) st = m+1; else dr = m;
    }
    int dupa = st;
    if (prima == dupa) cout << "NU EXISTA\n";
    else cout << prima+1 << ' ' << dupa << ' ' << dupa-prima << '\n';
}

De ce intervalul se micșorează

La început, frontiera căutată este în intervalul de posibilități dintre 0 și n. Testăm numai m<n. Dacă elementul este prea mic pentru prima frontieră, toate pozițiile până la m sunt eliminate și st devine m+1. Altfel, frontiera poate fi m sau una anterioară, deci dr devine m. Când st=dr, frontiera este determinată.

A doua căutare păstrează aceeași structură, dar elimină și valorile egale. Nu accesăm a[n]; n este o poziție posibilă pentru frontieră, nu un element al vectorului. În varianta clasică, capacitatea este 1000, iar n dă numărul de elemente valide.

Fiecare căutare consumă O(log(n+1)) timp și O(1) memorie auxiliară. Citirea datelor consumă O(n), separat de căutare. Biblioteca standard oferă lower_bound și upper_bound pentru aceste două operații; implementarea de aici explică logica lor pe întregi.

Exersează

Testează x mai mic decât toate valorile, x mai mare decât toate și x între două valori consecutive. În toate aceste cazuri, cele două frontiere coincid. Pentru 4 4 4, x=4, obții 1 3 3. Pentru n=0, buclele nu execută niciun acces.

Ca exercițiu, calculează câte valori sunt strict mai mici decât x: răspunsul este prima frontieră. Câte sunt mai mari? Scazi a doua frontieră din n. Aceste numărări reutilizează aceeași convenție, fără parcurgeri suplimentare.

Revezi căutarea binară de bază, lower_bound și iteratori și ordonarea datelor.

Întrebări frecvente

Cum găsesc prima și ultima apariție prin căutare binară?

Într-un vector sortat, caută prima poziție cu valoare cel puțin x și prima poziție cu valoare strict mai mare decât x. Dacă intervalul dintre ele nu este gol, el conține exact aparițiile lui x.

De ce nu opresc căutarea binară la prima egalitate?

Egalitatea găsită la mijloc nu garantează prima sau ultima apariție. Pentru o frontieră trebuie continuată căutarea în partea în care pot exista alte valori egale.

Cum aflu numărul aparițiilor fără să parcurg duplicatele?

Scade poziția primei valori cel puțin egale cu x din poziția primei valori strict mai mari. Diferența este numărul aparițiilor și se obține prin două căutări O(log n) pe un tablou sortat.