De ce contează?
Pe un raft de bibliotecă, cărțile sunt așezate în ordine crescătoare după numărul de cota. Vine cineva și îți cere „prima carte cu numărul cel puțin 47”. Nu citești fiecare cotă de la stânga la dreapta — sari direct la mijlocul raftului și, după câteva sărituri, te oprești fix la prima carte care nu mai e sub 47. Exact asta face lower_bound: pe un vector sortat, găsește instant prima poziție unde valoarea nu mai e mai mică decât cea cerută.
Intuiția
std::lower_bound(v.begin(), v.end(), x) îți dă un iterator către primul element din vector care este mai mare sau egal cu x — adică primul element care nu mai e mai mic decât x. Vectorul trebuie să fie sortat crescător. Pentru că merge prin înjumătățire (căutare binară), găsește acea poziție în O(log n), fără să parcurgă tot vectorul.
Gândește-te la el ca la „unde aș putea insera x ca să păstrez ordinea”: toate elementele dinainte sunt strict mai mici, iar de la poziția întoarsă încolo toate sunt mai mari sau egale.