First True Binary Search

First true binary search finds the first index where a monotone Boolean predicate becomes true. It generalizes lower bound from array values to any ordered search space.

The predicate must have the form:

Once the predicate becomes true, it must remain true.

Problem

Given indices from $0$ to $n - 1$ and a predicate $P(i)$, find the smallest index $i$ such that

If no such index exists, return $n$.

Key Idea

Maintain a half-open interval $[l, r)$ that contains the first true position. At each step, test the midpoint.

If $P(m)$ is true, the answer is at $m$ or to its left. Otherwise, the answer is to the right.

Algorithm

first_true(n, P):
    l = 0
    r = n

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

        if P(m):
            r = m
        else:
            l = m + 1

    return l

Example

Let the predicate values be:

The first true index is $3$.

Relation to Lower Bound

Lower bound is a special case where

So:

lower_bound(A, x):
    return first_true(length(A), lambda i: A[i] >= x)

Correctness

The invariant is:

• The answer is always inside $[l, r)$

When $P(m)$ is true, no index greater than $m$ is needed to find the first true position, so the right boundary moves to $m$.

When $P(m)$ is false, monotonicity implies that every index $\le m$ is false, so the left boundary moves to $m + 1$.

When the interval is empty, $l = r$, and that position is the first true index or $n$ if none exists.

Complexity

Here $T_P$ is the cost of evaluating the predicate.

Use Cases

• Lower bound in sorted arrays
• Minimum feasible value
• First failing test
• First time a threshold is reached
• First day when a condition holds

Implementation

def first_true(n, pred):
    l, r = 0, n
    while l < r:
        m = l + (r - l) // 2
        if pred(m):
            r = m
        else:
            l = m + 1
    return l

func FirstTrue(n int, pred func(int) bool) int {
    l, r := 0, n
    for l < r {
        m := l + (r-l)/2
        if pred(m) {
            r = m
        } else {
            l = m + 1
        }
    }
    return l
}