// ── ABOUT ────────────────────────────────────────────────────────
// REQUIRES sorted container
// O(log n)
// Vector/STL → returns iterator
// Array → returns pointer (int*)
// lower_bound → first element >= value
// upper_bound → first element > value
vector<int> arr = {4, 5, 5, 6, 7, 8, 25}; // must be sorted
// ── LOWER BOUND ──────────────────────────────────────────────────
auto lb = lower_bound(arr.begin(), arr.end(), 5);
cout << *lb; // 5 (first element >= 5)
lb = lower_bound(arr.begin(), arr.end(), 6);
cout << *lb; // 6
lb = lower_bound(arr.begin(), arr.end(), 2);
cout << *lb; // 4 (2 not present → next greater)
lb = lower_bound(arr.begin(), arr.end(), 26);
if (lb == arr.end())
cout << "not found"; // 26 > all elements
// ── UPPER BOUND ──────────────────────────────────────────────────
auto ub = upper_bound(arr.begin(), arr.end(), 5);
cout << *ub; // 6 (first element > 5, skips both 5s)
ub = upper_bound(arr.begin(), arr.end(), 6);
cout << *ub; // 7
ub = upper_bound(arr.begin(), arr.end(), 26);
if (ub == arr.end())
cout << "not found";
// ── INDEX FROM ITERATOR ──────────────────────────────────────────
int idx = lower_bound(arr.begin(), arr.end(), 5) - arr.begin(); // index = 1
// ── IN ARRAY ─────────────────────────────────────────────────────
int a[] = {4, 5, 5, 6, 7, 8, 25};
int n = 7;
int *ptr = lower_bound(a, a + n, 6); // returns pointer
cout << *ptr; // 6
// ── IN SET / MAP ─────────────────────────────────────────────────
set<int> s = {1, 3, 5, 7};
s.lower_bound(4); // iterator to 5
s.upper_bound(5); // iterator to 7
map<int, string> m;
m.lower_bound(3); // applies on KEY only