Maintain closed [lo,hi] known to contain the answer. If mid is True, keep mid with hi=mid; otherwise exclude it with lo=mid+1, terminating at lo=hi.
Recognition signals
The request says first, leftmost, at least, or lower bound.
A predicate becomes true at one point and stays true.
Duplicates make an arbitrary equality hit insufficient.
The initialization contains a known answer or a true sentinel can be supplied.
False friends
Signal
Why it is different
Any exact hit
When no boundary is requested, ordinary exact binary search is clearer.
Nonmonotone predicate
If truth alternates, discarding half has no logical support.
Core invariant
The first True always lies in [lo,hi]; indexes left of lo are proven False, while hi remains a feasible candidate.
State, transition, and processing order
Item
Definition
State
lo, hi, mid, and monotone predicate; this form assumes at least one True inside the interval.
Transition
If predicate(mid) is True, set hi=mid; otherwise set lo=mid+1.
Frontier / order
The closed interval of possible transition points; a True mid cannot be discarded because it may be the answer.
Python skeleton
def first_true(lo, hi, predicate):
# Precondition: predicate(hi) is True.
while lo < hi:
mid = lo + (hi - lo) // 2
if predicate(mid):
hi = mid
else:
lo = mid + 1
return lo
Correctness sketch
If mid is True, monotonicity only proves the answer is not to its right; mid itself can be first, so retain [lo,mid].
If mid is False, mid and everything left are impossible first-True positions, so retain [mid+1,hi].
The interval strictly shrinks to one point, and the invariant plus existence makes that point the first True.
Complexity
Time
Space
Parameters
O(log N) predicate calls
O(1) beyond predicate space
N=hi-lo+1; for predicate cost C, total time is O(C log N).
Edge cases
If lo is already True, return lo.
If only hi is True, convergence still reaches hi.
When no True may exist, add a true sentinel or validate the returned candidate.
Real-valued search needs an iteration or tolerance stopping rule instead.
Error patterns
Pattern
Why it fails / fix
Using hi=mid-1 on True
That discards a mid which may be the first True.
Mixing while lo<=hi with hi=mid
Inconsistent interval semantics can create an infinite loop.
Assuming monotonicity
A few friendly examples do not prove the predicate has only one transition.
Selection and exclusion rules
Write the picture F F | T T before choosing updates.
Use the single-point form when predicate(hi) is provably True.
For last True, invert the predicate or use the symmetric upper-mid form.