guest@cp-base:~/home/binary-search$
templates/lower-bound.cpp
compilable
$cat templates/lower-bound

Lower Bound

Find the first element >= target in a sorted array using binary search.

[Binary Search]|
Jul 9, 2026
|explanatory_notes.md|
#binary-search#lower-bound#predicate
Log in to track progress, save custom versions, and organize into collections.Log In
$cat source_code/
cpp
01
02
03
04
05
06
07
08
09
10
11
12
#include <bits/stdc++.h>
using namespace std;

int lowerBound(vector<int>& a, int target) {
    int l = 0, r = (int)a.size() - 1, ans = -1;
    while (l <= r) {
        int m = l + (r - l) / 2;
        if (a[m] >= target) { ans = m; r = m - 1; }
        else l = m + 1;
    }
    return ans;
}
12 linesutf-8
$cat explanation_notes.md
notes_viewer --renderedmarkdown (math enabled)

Lower Bound

Finds the first element ≥\ge target in a sorted array. Equivalent to std::lower_bound.

How It Works

  • If a[m]≥a[m] \ge target, record mm as candidate and search left

  • Otherwise, search right

  • Returns the leftmost valid position, or −1-1 if all elements are smaller

    • When to Use

  • First occurrence of a value in sorted array

  • Insertion point for a value

  • Finding the first true in a monotonic predicate

    • Complexity

  • Time — O(log⁡n)O(\log n)

  • Space — O(1)O(1)