Monotone Predicate Search

Monotone predicate search finds the transition point of a Boolean predicate over an ordered domain. It is the abstract form behind lower bound, upper bound, first true search, last true search, and binary search on answer.

A predicate is monotone if its values change at most once.

For first true search, the shape is:

false, false, false, true, true, true

For last true search, the shape is:

true, true, true, false, false, false

Problem

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

P(i) = true

If no such index exists, return $n$ .

Key Idea

Because the predicate changes value only once, the answer is a boundary. Binary search can locate that boundary without checking every index.

At each step, test the midpoint:

If $P(m)$ is true, keep the left half
If $P(m)$ is false, keep the right half

Algorithm

monotone_predicate_search(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

Suppose:

index	0	1	2	3	4	5
P(i)	false	false	false	true	true	true

The first true index is:

3

The algorithm returns $3$ .

Correctness

The algorithm maintains this invariant:

The first true index, if it exists, lies in the half-open interval $[l, r)$ .

If $P(m)$ is true, then $m$ is a valid true position, but an earlier true position may exist. Therefore the answer lies in $[l, m]$ , and the algorithm sets $r = m$ .

If $P(m)$ is false, monotonicity implies that every index at or before $m$ is false. Therefore the first true index must lie in $[m + 1, r)$ , and the algorithm sets $l = m + 1$ .

When $l = r$ , the interval contains exactly one boundary position. That position is the first true index, or $n$ if no true value exists.

Complexity

Let $T_P$ be the cost of evaluating the predicate.

cost	value
predicate evaluations	$O(\log n)$
total time	$O(T_P \log n)$
extra space	$O(1)$

Common Instances

algorithm	predicate
lower bound	$A[i] \ge x$
upper bound	$A[i] > x$
binary search on answer	candidate value is feasible
bisection method	sign or threshold condition
Fenwick lower bound	prefix sum reaches target

Last True Form

For a predicate shaped as:

true, true, true, false, false, false

find the last true index by searching for the first false index and subtracting one.

last_true(n, P):
    first_false = monotone_predicate_search(n, lambda i: not P(i))
    return first_false - 1

If no index is true, the result is $-1$ .

When to Use

Use monotone predicate search when:

the domain is ordered
the predicate has one transition
checking a candidate is cheaper than scanning
the desired answer is a boundary

Notes

The hardest part is proving monotonicity.
The predicate may be implicit and expensive.
The method works on integers directly.
For real domains, use a fixed number of iterations or a tolerance.

Implementation

def monotone_predicate_search(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 MonotonePredicateSearch(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
}