Lower Bound

Lower bound finds the first index at which a value $x$ can be inserted in a sorted array while preserving order. It returns the smallest index $i$ such that

A[i] \ge x

If all elements are smaller than $x$ , it returns $n$ .

This operation forms the basis of many ordered data structure queries, including range queries and duplicate handling.

Problem

Given a sorted array $A$ of length $n$ and a value $x$ , find the smallest index $i$ such that

A[i] \ge x

Return $n$ if no such index exists.

Key Idea

The predicate

A[i] \ge x

is monotone:

false for small indices
true for large indices

Binary search can locate the first true position.

Algorithm

Maintain a half-open interval $[l, r)$ .

lower_bound(A, x):
    l = 0
    r = length(A)

    while l < r:
        m = l + (r - l) // 2

        if A[m] < x:
            l = m + 1
        else:
            r = m

    return l

Example

Let

A = [1, 3, 3, 5, 7]

and

x = 3

Steps:

step	r	m	A[m]	action
1	5	2	3	move left
2	2	1	3	move left
3	1	0	1	move right

Return index $1$ .

Interpretation

All indices $< i$ satisfy $A[j] < x$
All indices $\ge i$ satisfy $A[j] \ge x$

This partitions the array.

Correctness

Invariant:

The answer always lies in $[l, r)$

Each step reduces the interval while preserving:

left side contains only false values
right side contains only possible true values

When $l = r$ , the first true index has been isolated.

Complexity

case	time
all cases	$O(\log n)$

Space:

O(1)

Use Cases

Insert position in sorted array
Count elements less than $x$
Range queries: combine with upper bound
Deduplication boundaries

Implementation

def lower_bound(a, x):
    l, r = 0, len(a)
    while l < r:
        m = l + (r - l) // 2
        if a[m] < x:
            l = m + 1
        else:
            r = m
    return l

func LowerBound(a []int, x int) int {
    l, r := 0, len(a)
    for l < r {
        m := l + (r-l)/2
        if a[m] < x {
            l = m + 1
        } else {
            r = m
        }
    }
    return l
}