# Monotone Predicate Search

# 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

```text id="mono-pred-1"
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.

```text id="mono-pred-last"
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

```python id="py-mono-pred"
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
```

```go id="go-mono-pred"
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
}
```