Deriving Last-True Search from First-True Boundaries

Good to see you again. In the previous lesson, you derived a robust half-open first-true search: it finds the first index where a false-then-true predicate changes state, returning n if no true value exists.

This lesson derives last true rather than treating it as a second template to memorize. The central move is to recognize that “last true” is the position immediately before the first false. You will translate that observation into a loop, a contract, and a C++ implementation that handles all-true, all-false, and empty domains cleanly.

---

From last true to first true

Suppose $Q(i)$ has this monotonic form over indices $0$ through $n-1$:

$$[T,T,\dots ,T,F,F,\dots ,F]$$

The problem is to find the greatest index $i$ for which $Q(i)$ is true. If no index is true, the natural sentinel answer is $-1$.

Instead of inventing a new kind of search, negate the predicate:

$$P(i)=\neg Q(i)$$

Now the sequence becomes:

$$[F,F,\dots ,F,T,T,\dots ,T]$$

That is exactly the first-true form from the previous lesson.

Let $b$ be the first index where $P$ is true:

$$b=\min \{i\mid P(i)=\text{true}\}$$

Since $P(i)$ means $Q(i)$ is false, $b$ is the first false index for $Q$. Therefore the last true index is one position earlier:

$$\text{last true}(Q)=b-1$$

Equivalently,

$$\boxed{\text{last true}(Q)=\text{first true}(\neg Q)-1}$$

This identity is the derivation. The rest is just expressing it faithfully in code.

Consider a concrete predicate:

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

Negating it gives:

$$[\neg Q(0),\neg Q(1),\neg Q(2),\neg Q(3),\neg Q(4),\neg Q(5)]=[F,F,F,F,T,T]$$

The first true index of $\neg Q$ is $4$, hence the last true index of $Q$ is:

$$4-1=3$$

The subtraction is not a trick or a patch. It expresses the exact relationship between adjacent boundary positions.

---

Rewrite the first-true loop mechanically

Recall the first-true template for a predicate $P$:

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)) {
            hi = mid;
        } else {
            lo = mid + 1;
        }
    }

    return lo;
}

To obtain last true for $Q$, call this function with $P(i)=\neg Q(i)$:

template <class Pred>
int last_true(int n, Pred Q) {
    return first_true(n, [&](int i) {
        return !Q(i);
    }) - 1;
}

This version is excellent during development because the relationship is explicit. It says precisely what the algorithm is doing: find the first invalid position, then step back once.

For competitive programming or interviews, you will often write the inlined version. Start with the substitution:

$$P(mid)=\neg Q(mid)$$

The first-true branch

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

becomes:

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

and, written in the more natural branch order:

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

So the complete half-open last-true template is:

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

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

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

    return lo - 1;
}

The endpoint lo is the first false position. The final answer is the element immediately before it.

Why the updates reverse

The update directions can be derived from the goal of finding the first false:

• If $Q(mid)$ is true, then mid cannot be the first false position. It belongs to the known-true prefix, so discard it:

  lo = mid + 1;
  

• If $Q(mid)$ is false, then mid could be the first false position. Retain it as a candidate:

  hi = mid;
  

This is the same asymmetry as first true, with true and false interchanged.

Search objective	Predicate pattern	Midpoint is in candidate boundary position when…	Update
First true	$F,\dots ,F,T,\dots ,T$	P(mid) is true	hi = mid
Last true	$T,\dots ,T,F,\dots ,F$	Q(mid) is false, because it may be the first false	hi = mid

For last true, you are not directly retaining a “last true candidate” during the half-open loop. You are locating the first false boundary and converting that boundary to the final true index afterward.

---

The invariant, stated in the new vocabulary

A correct implementation should have a contract you can say aloud before writing code.

For last_true(n, Q), assume $Q$ is monotone in the form:

$$Q(i)=\text{true}⟹Q(j)=\text{true}\text{for every }j\le i$$

Equivalently:

$$Q(i)=\text{false}⟹Q(j)=\text{false}\text{for every }j\ge i$$

During the loop, maintain:

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

Thus:

• positions before lo are proved true;
• positions from hi onward are proved false;
• the unknown transition lies in $[lo,hi)$.

When the loop finishes, lo == hi. Call this position $b$. It is the first false position, including the possibility $b=n$. Consequently,

$$\text{last true}=b-1=lo-1$$

Notice how the sentinel $-1$ arises without special-case code. If $b=0$, then no index can be true, and $b-1=-1$.

A trace

Let:

$$Q=[T,T,T,T,F,F,F]$$

The expected last true index is $3$.

Step	lo	hi	mid	$Q(mid)$	Resulting knowledge
Initial	0	7	—	—	No positions classified
1	0	7	3	true	Indices $0$ through $3$ are true; set lo = 4
2	4	7	5	false	Indices $5$ and $6$ are false; set hi = 5
3	4	5	4	false	Index $4$ is false; set hi = 4
Final	4	4	—	—	First false is $4$; return $4-1=3$

The loop did not search right merely because it “wanted a larger answer.” A true midpoint proved that the first false must occur strictly after mid. Every move follows from the boundary contract.

---

Edge cases are part of the contract

The formula return lo - 1 deals with the important cases uniformly.

Predicate $Q$ over the domain	Final lo / first false	Returned last true
Empty domain	$0$	$-1$
$F,F,F$	$0$	$-1$
$T$	$1$	$0$
$T,T,T$	$3$	$2$
$T,T,F,F$	$2$	$1$

Two details matter:

1. All true: there is no actual false element, but the conceptual first-false position is the one-past-the-end position $n$. Returning $n-1$ correctly gives the final valid index.

2. All false: the first-false position is $0$. Returning $-1$ correctly signals that no valid index exists.

Avoid changing the loop condition or adding a separate ans variable merely to handle these cases. The half-open boundary contract has already accounted for them.

---

Sorted-array application: last occurrence through a boundary

For a sorted vector a, define:

$$Q(i)\equiv a[i]\le \text{target}$$

Because the vector is sorted, this predicate has the required shape:

$$[T,T,\dots ,T,F,F,\dots ,F]$$

Therefore:

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

pos is the greatest index whose value is at most target.

That is close to “last occurrence of target,” but not identical. If target is absent, pos may identify the predecessor of target, not an occurrence. Validate the result:

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

    if (pos >= 0 && a[pos] == target) {
        return pos;
    }
    return -1;
}

For example, with:

$$a=[1,4,4,4,9,12]$$

• For target = 4, the predicate $a[i]\le 4$ is:

  $$[T,T,T,T,F,F]$$

  so last_true returns $3$, the last occurrence of $4$.

• For target = 7, the predicate is still:

  $$[T,T,T,T,F,F]$$

  and last_true again returns $3$. But a[3] is $4$, not $7$, so the target is absent.

This distinction will matter whenever a boundary is used to answer an exact-match question: the boundary identifies a structural position; a final value check determines whether the requested value actually occurs.

---

A compact implementation checklist

When a problem asks for the greatest integer or index satisfying a condition, use this sequence:

1. Define $Q(x)$: “is $x$ valid?”
2. Prove the pattern is true then false as $x$ increases.
3. Search for the first $x$ where $Q(x)$ is false.
4. Return one position before that boundary.
5. Decide whether $-1$ is an appropriate “no valid answer” sentinel for the problem.

For the implementation, retain the four lines that encode the derivation:

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

    if (Q(mid)) lo = mid + 1;
    else        hi = mid;
}
return lo - 1;

For a short practice session, implement last_true first by calling your existing first_true with !Q, then inline the loop. Differential-test both versions on randomly generated true-prefix/false-suffix Boolean vectors, including an empty vector and the all-true/all-false cases. They should always produce the same answer.

---

Conclusion

Last true is not a disconnected binary-search template:

$$\boxed{\text{last true}(Q)=\text{first true}(\neg Q)-1}$$

The half-open loop therefore maintains a known-true prefix and a known-false suffix:

• a true midpoint is definitely before the first false, so set lo = mid + 1;
• a false midpoint may be the first false, so set hi = mid;
• at termination, lo is the first false position and lo - 1 is the last true position.

Next, you will address a lower-level reliability issue that affects every variant: computing the midpoint safely when signed integer bounds can be large.