# Last True Binary Search

# 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

```id="lst9p2"
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

```id="py-last-true"
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
```

```id="go-last-true"
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
}
```