lower_bound — prima poziție ≥ valoare

De ce contează?

Într-o sală de cinema cu locuri numerotate crescător, vrei primul scaun liber cu numărul cel puțin 50. Nu te uiți la toate — sari direct la zona 50 și iei primul de acolo în sus. lower_bound face exact această săritură, prin căutare binară.

Ce face `lower_bound`

Pe un vector sortat, lower_bound găsește prima poziție unde elementul este ≥ x (primul element care nu e mai mic decât x). Întoarce un iterator (pe vector clasic, un pointer) spre acel element.

int *p = lower_bound(v, v + n, x);

Spre deosebire de binary_search (care zice doar dacă x există), lower_bound îți dă locul.

Observația-cheie

„Lower bound" = marginea de jos a zonei valorilor ≥ x. Dacă x există, e prima lui apariție; dacă nu, e locul unde ar trebui inserat ca vectorul să rămână sortat.

De la pointer la index

Rezultatul e un pointer. Pe un vector clasic, scazi începutul ca să obții poziția numerică:

int poz = lower_bound(v, v + n, x) - v;   // index 0-based

Exemplu concret

Vectorul sortat v = {2, 4, 4, 6, 8}. Câteva cazuri:

lower_bound(..., 4)  -> poz 1  (prima aparitie a lui 4)
lower_bound(..., 5)  -> poz 3  (primul >= 5 este 6)
lower_bound(..., 1)  -> poz 0  (toate sunt >= 1)
lower_bound(..., 9)  -> poz 5  (= n, niciunul >= 9)

Observă cazul 5: nu există în vector, dar lower_bound îți dă locul unde s-ar insera.

Implementare C++

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

int main() {
    int v[5] = {2, 4, 4, 6, 8};   // SORTAT
    int n = 5;

    int poz = lower_bound(v, v + n, 5) - v;
    cout << poz << "\n";   // 3

    // verificare daca x exista chiar la acea pozitie
    int x = 4;
    int *p = lower_bound(v, v + n, x);
    if (p != v + n && *p == x)
        cout << "exista pe pozitia " << (p - v) << "\n";  // exista pe pozitia 1
    else
        cout << "nu exista\n";
    return 0;
}

binary_search se poate exprima prin lower_bound: x există dacă poziția e validă și elementul de acolo e chiar x.

Aplicații tipice

Câte elemente sunt < x: chiar lower_bound(...) - v.
Verificare existență + poziție: combinația de mai sus.
Inserare ordonată: locul corect e exact lower_bound.

Complexitate

Operație	Timp	Spațiu
`lower_bound`	O(log n)	O(1)

Vizualizare

În spatele lui lower_bound stă o căutare binară. Urmărește cum intervalul de căutare se înjumătățește pas cu pas până la prima poziție unde elementul nu mai e mai mic decât valoarea căutată:

Greșeli frecvente

Capcane la lower_bound:

Vector nesortat: rezultat nedefinit. Sortează întâi.
Dereferențiezi v + n: dacă toate elementele sunt < x, lower_bound întoarce capătul. *p acolo e acces invalid. Verifică p != v + n înainte.
Confuzi „există" cu „poziția": lower_bound dă locul primului ≥ x, nu garantează că x e acolo. Confirmă cu *p == x.
Uiți - v: rezultatul e un pointer, nu un index. Pentru poziție numerică scazi începutul.

Recapitulare

lower_bound întoarce un iterator spre primul element ≥ x, pe vector sortat, în O(log n).
Pentru index scazi începutul (- v); pentru existență verifici p != v+n && *p == x.
Dacă niciun element nu e ≥ x, rezultatul e capătul v + n — tratează acest caz înainte de a dereferenția.