Last True Binary Search

Last true binary search finds the last index where a monotone Boolean predicate is true. It is the mirror form of first true binary search.

The predicate must have the form:

$$ true, true, true, false, false, false $$

Once the predicate becomes false, it must remain false.

Problem

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

$$ P(i) = true $$

If no such index exists, return $-1$.

Key Idea

Maintain a half-open interval $[l, r)$ where the answer may exist. Test the midpoint, but bias the update toward the right side when the predicate is true.

If $P(m)$ is true, then $m$ is a valid answer, and the last true position may be at $m$ or to its right. If $P(m)$ is false, the answer must be to the left.

Algorithm

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

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

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

    return l - 1

Example

Let the predicate values be:

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

The last true index is $3$.

The algorithm returns $4 - 1 = 3$.

Relation to Upper Bound

If a sorted array is searched for the last element satisfying

$$ A[i] \le x $$

then the predicate is true first and false later. Last true search returns the last index whose value is at most $x$.

Equivalently:

$$ \text{last_true}(A[i] \le x) = \text{upper_bound}(A, x) - 1 $$

Correctness

The algorithm maintains this invariant:

• All indices before $l$ have already been accepted as true candidates.
• All indices from $r$ onward have already been rejected or lie after the transition.
• The transition from true to false lies inside $[l, r)$.

When $P(m)$ is true, monotonicity implies that every index before $m$ is also true, so the last true index must be at $m$ or to the right. The algorithm moves $l$ to $m + 1$.

When $P(m)$ is false, monotonicity implies that every index after $m$ is also false, so the last true index must be to the left. The algorithm moves $r$ to $m$.

When the loop terminates, $l = r$ is the first false index. Therefore the last true index is $l - 1$.

Complexity

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

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

Use Cases

• Last valid prefix length
• Last index with value $\le x$
• Maximum feasible answer
• Last successful test case
• Right boundary of a sorted range

Implementation

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

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