Invariant-Preserving Updates for First-True Search

Hello again. Last time, you established the half-open first-true contract: for a monotone predicate $P$, return the first position $b$ where $P$ is true, returning $n$ when every array element is false. You also established the invariant that everything before lo is known false, everything from hi onward is known true, and the boundary remains bracketed by $[lo,hi]$.

Now we make the loop body inevitable. Rather than memorizing hi = mid and lo = mid + 1, you will derive each assignment from the invariant and from exactly what one predicate evaluation proves. This is the transferable skill behind reliable binary-search variants.

---

The update rule follows the meaning of the bounds

Recall the first-true invariant for an integer domain $0,\dots ,n-1$:

$$0\le lo\le hi\le n$$ $$\forall i\in [0,lo),P(i)=\text{false}$$ $$\forall i\in [hi,n),P(i)=\text{true}$$

The active element range is $[lo,hi)$. The first-true boundary $b$, however, is a position, so it is bracketed by:

$$lo\le b\le hi$$

While lo < hi, choose:

int mid = lo + (hi - lo) / 2;

Because mid lies in the active interval,

$$lo\le mid<hi$$

so mid is always a valid index. The only remaining question is: once we evaluate P(mid), which portion of the array can be classified with certainty?

---

The difference between these two formulations is worth making explicit:

Formulation	Meaning of left-side variable after a false midpoint
Sentinel bracket	It stores the index of a known-false element, so use l = mid.
Half-open first true	It stores the first index not already known false, so use lo = mid + 1.

The evidence is identical. The variable contracts are different.

---

Case 1: the midpoint is true

Suppose:

$$P(mid)=\text{true}$$

Since $P$ is monotone, every later index is also true:

$$\forall i\ge mid,P(i)=\text{true}$$

This adds mid and everything to its right to the known-true region.

Crucially, mid might be the first true index. Therefore, discarding it would be unsound. The boundary can equal mid:

$$b=mid$$

So the new upper bound must retain mid as a possible boundary position:

hi = mid;

Formal invariant preservation

Let the updated variables be:

$$l{o}^{\prime }=lo,h{i}^{\prime }=mid$$

We verify each invariant clause.

1. Bounds remain valid. Since the loop is running, $lo<hi$, and the midpoint satisfies $lo\le mid<hi$. Therefore:

$$0\le l{o}^{\prime }\le h{i}^{\prime }\le n$$

2. The known-false prefix remains correct. It is unchanged:

$$[0,l{o}^{\prime })=[0,lo)$$

Every index there was already known false.

3. The known-true suffix expands correctly. The new true suffix is:

$$[h{i}^{\prime },n)=[mid,n)$$

At mid, the predicate evaluation directly gave true. At every index after mid, monotonicity gives true. Hence:

$$\forall i\in [h{i}^{\prime },n),P(i)=\text{true}$$

The invariant survives.

A useful way to say this in an interview is:

A true midpoint proves the boundary is at or left of mid; because mid itself may be the first true position, I set hi = mid.

---

Case 2: the midpoint is false

Now suppose:

$$P(mid)=\text{false}$$

Monotonicity tells us that no earlier index can be true. If some $i\le mid$ had $P(i)=\text{true}$, monotonicity would force $P(mid)$ to be true too, contradicting the observation.

Thus:

$$\forall i\le mid,P(i)=\text{false}$$

The entire range through mid is now known false. Since a first-true boundary cannot occur at a false index, the new lower bound should begin immediately after mid:

lo = mid + 1;

Formal invariant preservation

Let:

$$l{o}^{\prime }=mid+1,h{i}^{\prime }=hi$$

Again, verify the invariant mechanically.

1. Bounds remain valid. We know $mid<hi$. Since bounds are integers:

$$mid+1\le hi$$

Therefore:

$$0\le l{o}^{\prime }\le h{i}^{\prime }\le n$$

2. The known-false prefix expands correctly. The new false prefix is:

$$[0,l{o}^{\prime })=[0,mid+1)$$

Every index in this interval is at most mid, and has therefore been proved false.

3. The known-true suffix remains correct. It is unchanged:

$$[h{i}^{\prime },n)=[hi,n)$$

Those indices were already known true under the old invariant.

So the update preserves the invariant.

The corresponding interview-quality explanation is:

A false midpoint proves that the boundary is strictly right of mid. I discard mid along with the entire left half, setting lo = mid + 1.

The distinction between “at or left of” and “strictly right of” is exactly where the asymmetric +1 comes from.

---

One trace, interpreted as accumulated proof

Consider this monotone predicate:

$$[P(0),P(1),P(2),P(3),P(4),P(5),P(6)]=[F,F,F,T,T,T,T]$$

The answer is $b=3$.

Step	lo	hi	mid	Result	What has now been proved
Initial state	0	7	—	—	No indices classified yet
1	0	7	3	true	Indices $3$ through $6$ are true; set hi = 3
2	0	3	1	false	Indices $0$ and $1$ are false; set lo = 2
3	2	3	2	false	Index $2$ is also false; set lo = 3
Final state	3	3	—	—	The boundary must be position $3$

At every row, the implementation does not “guess” which half to search. It makes a stronger statement:

• A false result enlarges the proved-false prefix.
• A true result enlarges the proved-true suffix.
• The unresolved range contains only positions that could still be the boundary.

When lo and hi meet, no uncertainty remains.

---

Why nearby-looking updates fail

The correct updates are not arbitrary stylistic choices. Some alternatives violate the invariant immediately; others preserve enough information to look plausible but fail to make progress.

Observation	Incorrect update	What goes wrong
P(mid) is true	lo = mid + 1	This places a known-true mid inside the claimed false prefix. It can also discard the actual answer when $b=mid$.
P(mid) is true	hi = mid - 1	This can discard mid, even though it may be the first true index.
P(mid) is false	hi = mid	The new true suffix would include a midpoint known to be false.
P(mid) is false	lo = mid	It leaves mid, already known false, in the unresolved range. With hi = lo + 1, mid equals lo, so the loop can repeat forever.
P(mid) is true	hi = mid + 1	It retains an extra index and can fail to shrink a one-element active range.

The key lesson is slightly deeper than “remember the plus one.” An update needs both properties:

1. Preservation: it must not contradict the false-prefix and true-suffix classifications.
2. Progress: it must shrink the unresolved interval whenever the loop runs.

For the half-open contract, the strongest safe eliminations are precisely:

if (P(mid)) {
    hi = mid;
} else {
    lo = mid + 1;
}

---

The complete first-true loop

Here is the template whose body you have now derived rather than memorized:

template <class Pred>
int first_true(int n, Pred P) {
    int lo = 0;
    int hi = n;

    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;

        if (P(mid)) {
            // P(mid) is true, so every index in [mid, n) is true.
            // mid could be the first true position.
            hi = mid;
        } else {
            // P(mid) is false, so every index in [0, mid + 1) is false.
            lo = mid + 1;
        }
    }

    return lo;
}

For a sorted vector a, this becomes lower-bound behavior:

int pos = first_true(static_cast<int>(a.size()),
                     [&](int i) { return a[i] >= target; });

The function returns the first position where inserting target would preserve sorted order. If target is absent, pos is still meaningful: it is the insertion position. If target is larger than every element, the predicate is all false and the function returns a.size().

---

Deliberate implementation practice

Spend about 10–15 minutes turning the template into a habit without treating it as a magic incantation.

1. Implement first_true from a blank editor, including the invariant as a comment.
2. Test it on Boolean vectors represented by a lambda over a vector<bool> or vector<int>.
3. For each case, record lo, hi, mid, and the predicate result until termination.

Use at least these boundary patterns:

Predicate values	Expected first-true position
empty domain	0
$F$	1
$T$	0
$F,F,F$	3
$T,T,T$	0
$F,T,T,T$	1
$F,F,T,T$	2
$F,F,F,T,T$	3

While tracing, do not merely check the final answer. At each iteration, verify the invariant:

• every index before lo is false;
• every index from hi onward is true;
• the known boundary remains between lo and hi.

That check catches flawed updates before a test case happens to expose them.

---

Conclusion

The first-true updates follow directly from the classification invariant:

• If $P(mid)$ is true, mid may be the first true position, so retain it with hi = mid.
• If $P(mid)$ is false, the boundary lies strictly after it, so discard it with lo = mid + 1.
• The updates are asymmetric because a true midpoint must remain a candidate, while a false midpoint cannot be one.
• Correct binary search needs both invariant preservation and strict interval shrinkage.

Next, you will derive a last-true search from this same boundary reasoning, rather than learning a disconnected second template.