# First True Binary Search

# 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:

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

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

$$
P(i) = true
$$

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

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

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

The first true index is $3$.

## Relation to Lower Bound

Lower bound is a special case where

$$
P(i) \equiv A[i] \ge x
$$

So:

```id="lb-as-ft"
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

| 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

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

## Implementation

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

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