Choosing Search Bounds to Preserve Boundary Contracts

Hello again. In the previous lesson, you established the prerequisite for binary search: a predicate must be monotone over a clearly ordered domain. For a first-true search, its values have the form false values followed by true values.

Now comes the implementation decision that causes many off-by-one bugs: what do your bounds mean? An interval such as $[lo,hi]$ or $[lo,hi)$ is not merely notation. It is a contract governing which candidates remain unresolved, what happens on empty input, and whether a “not found” result can be represented safely.

By the end of this lesson, you should be able to select inclusive or half-open bounds deliberately, state the result contract they support, and derive the matching loop guard and updates without mixing conventions.

---

Start with the boundary contract, not the loop

Let $P(i)$ be monotone over valid array indices $0$ through $n-1$:

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

The cleanest first-true contract is not “return an index containing true.” That wording fails when every value is false. Instead, define a boundary position $b$:

$$b=\min \left(\{i\in \{0,\dots ,n-1\}:P(i)\}\cup \{n\}\right)$$

This contract always has an answer:

• If some index is true, $b$ is the first true index.
• If all values are false, $b=n$.
• If $n=0$, $b=0$.

So the output is an insertion-style position in $[0,n]$, not necessarily a valid element index in $[0,n-1]$.

For a sorted vector and target x, this is exactly the contract behind a lower bound:

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

The returned boundary is the first position at which x could be inserted while preserving sorted order.

That distinction resolves several edge cases before any code exists. In particular, returning $n$ is not an error for a boundary search. It means “there is no true element among the array indices.”

---

Half-open bounds: make the empty range natural

The most useful first-true convention is a half-open unresolved interval:

$$[lo,hi)$$

Initialize it as:

$$lo=0,hi=n$$

Here, hi is exclusive: it may equal $n$, but P(hi) is never evaluated.

A precise interpretation during the search is:

• Every index strictly before lo is known false.
• Every index at or after hi is known true, if it is an actual array index.
• The boundary position $b$ lies between lo and hi, inclusive.

The remaining unclassified element indices are exactly those in $[lo,hi)$. Meanwhile, the boundary itself is a gap between indices, so it may equal either endpoint.

The matching updates

Choose

$$mid=lo+\lfloor \frac{hi-lo}{2}\rfloor$$

When lo < hi, this guarantees:

$$lo\le mid<hi$$

Thus mid is always a valid array index.

Now inspect $P(mid)$.

If $P(mid)$ is true, mid may be the first true index. You must not discard it as a possible boundary. Set:

$$hi=mid$$

This removes mid from the unresolved element interval, but retains it as the right endpoint of the possible boundary range.

If $P(mid)$ is false, neither mid nor anything left of it can be the first true index. Set:

$$lo=mid+1$$

The resulting first-true search is:

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;  // First true index, or n if none exists.
}

For now, focus on the contract rather than memorizing the template. A later lesson will formalize its invariant and prove why these updates preserve it.

Trace: a normal transition

Suppose:

$$P=[F,F,F,T,T]$$

Then $n=5$, and the first true boundary is $b=3$.

Iteration	lo	hi	mid	$P(mid)$	Action
Start	0	5	—	—	unresolved indices are $[0,5)$
1	0	5	2	false	lo = 3
2	3	5	4	true	hi = 4
3	3	4	3	true	hi = 3
End	3	3	—	—	return 3

The same code handles extreme cases without special branches:

Predicate pattern	Meaning	Returned boundary
$[T,T,T]$	all values qualify	$0$
$[F,F,F]$	no values qualify	$n$
empty array	no indices exist	$0$

The loop guard lo < hi is meaningful: it says that at least one unresolved element index remains. When lo == hi, the unresolved half-open interval is empty, and that shared position is the boundary.

---

Inclusive bounds: search actual indices, allow them to cross

An inclusive interval is written:

$$[lo,hi]$$

For an array, initialize it as:

$$lo=0,hi=n-1$$

Unlike the half-open form, an empty array begins with:

$$lo=0,hi=-1$$

That is valid: the inclusive interval $[0,-1]$ contains no indices.

With inclusive bounds, the natural loop guard is:

$$lo\le hi$$

This says that at least one valid array index remains to inspect.

For the same first-true boundary contract, use:

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

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

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

    return lo;  // First true index, or n if none exists.
}

This may look only one character different from the half-open version, but its logic is distinct.

Why does a true midpoint use hi = mid - 1 here?

In the inclusive formulation, hi denotes the last unclassified index. Once $P(mid)$ is true:

• mid is a valid candidate for the answer;
• every index strictly to its right is also true;
• the only possible improvement is a smaller true index.

So the still-unclassified region must end at mid - 1:

$$hi=mid-1$$

The boundary position mid has not been lost. It is represented by the fact that eventually lo can cross hi:

$$lo=hi+1$$

At termination, lo is precisely the first true position, or $n$ if no true index was found.

A useful inclusive interpretation is:

• indices before lo are known false;
• indices after hi are known true;
• the boundary belongs to $[lo,hi+1]$.

The $hi+1$ is important. It accounts for a boundary immediately after the final unresolved index.

The video uses an ans variable to remember the best true index seen so far. That is also correct:

int ans = n;

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

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

return ans;

For a first-true predicate, ans and lo end with the same value. The version returning lo is often easier to reason about because it directly returns the boundary position. The ans version can feel more natural when the required fallback is problem-specific, such as -1, an optional result, or a special object.

---

The two conventions are equivalent—but their rules are not interchangeable

Both styles solve the same contract:

$$\text{Return the smallest }i\in [0,n]\text{ such that }i=n\text{ or }P(i).$$

Their difference lies in what the bounds represent.

Design choice	Half-open formulation	Inclusive formulation
Unresolved indices	$[lo,hi)$	$[lo,hi]$
Initial bounds	lo = 0, hi = n	lo = 0, hi = n - 1
Empty-array state	lo == hi == 0	lo = 0, hi = -1
Loop guard	lo < hi	lo <= hi
On P(mid) == true	hi = mid	hi = mid - 1
On P(mid) == false	lo = mid + 1	lo = mid + 1
Result	lo	lo
No true index	returns n	returns n

The key distinction is the true case:

• In a half-open interval, hi = mid is progress because mid < hi before the update.
• In an inclusive interval, hi = mid can fail to make progress when lo == hi == mid. Therefore it must be hi = mid - 1.

This is not a stylistic preference. It is forced by the interval contract.

Two broken hybrids to recognize immediately

Hybrid 1: half-open initialization with an inclusive guard

int lo = 0, hi = n;
while (lo <= hi) {
    // ...
}

With $n=1$, a false predicate can move lo to 1. The next iteration still satisfies lo <= hi, and the code may attempt to evaluate P(1), which is outside the array.

Hybrid 2: inclusive initialization with a half-open guard

int lo = 0, hi = n - 1;
while (lo < hi) {
    // ...
}

With a singleton array, lo == hi == 0 initially, so the loop does not inspect the only element at all.

A compact diagnostic rule is:

Bounds, loop guard, and updates form one unit. Borrowing a line from another template breaks the proof unless you re-derive the contract.

---

Choosing a convention in C++ problem solving

For boundary searches over arrays, half-open bounds are usually the strongest default.

Use the half-open form when:

• the answer is naturally an insertion position;
• “not found” should be represented by n;
• empty ranges should work without a special case;
• you want reasoning aligned with iterator ranges such as [first, last);
• you are conceptually implementing std::lower_bound or std::upper_bound.

Use an inclusive form when:

• the problem naturally states an integer domain with inclusive endpoints;
• you want to search all values in a closed domain such as $L$ through $R$;
• you deliberately maintain a best-known answer;
• you are implementing classic exact-match search, where exiting after lo > hi naturally means the target is absent.

For example, suppose the candidate answer is a day from $1$ through $30$, and feasible(day) is false then true. Both contracts are valid:

Representation	Initial bounds	No feasible day
Half-open	$[1,31)$	returns 31
Inclusive	$[1,30]$	returns 31 after bounds cross

In either case, 31 is a sentinel boundary, not a valid day. If the problem requires -1 instead, convert only after the search:

int day = first_true(...);
return day == 31 ? -1 : day;

Keep the internal search contract uniform; perform output-format conversion at the boundary of the function.

One C++ caution follows from this choice. Inclusive array bounds often require hi = -1 for an empty range, so size_t is a poor type for that convention because it is unsigned. A half-open index range avoids negative bounds and is friendlier to size_t, although competitive-programming code often uses signed int or long long after checking that the domain fits. Midpoint overflow and signed sentinel bounds will receive dedicated treatment later.

---

A short pre-code contract checklist

Before writing any binary-search loop, write these facts on paper or in a comment:

1. Output: Is the answer an element index, an insertion position, a maximum feasible value, or a sentinel?
2. Domain: Are candidates valid at $[0,n-1]$, $[L,R]$, or some other interval?
3. Empty and extreme cases: What should all-false, all-true, and empty input return?
4. Convention: Are bounds inclusive or half-open?
5. Guard: Does it express “at least one unresolved candidate remains” for that convention?
6. Updates: When the midpoint is true or false, which side is proved irrelevant, and does the chosen update strictly reduce the unresolved region?

If each answer is explicit, the code is usually mechanical. If one is vague, an off-by-one error is likely waiting in the implementation.

---

Conclusion

A binary-search interval is a proof contract, not a pair of variables chosen by habit.

• A robust first-true contract returns a boundary position in $[0,n]$, with $n$ meaning “no true index exists.”
• Half-open bounds begin at $[0,n)$, use while (lo < hi), and update a true midpoint with hi = mid.
• Inclusive bounds begin at $[0,n-1]$, use while (lo <= hi), and update a true midpoint with hi = mid - 1.
• The same return value can arise from either convention, but their guards and updates cannot be mixed.
• Empty input, all-false input, and all-true input should follow directly from the stated contract rather than from special-case patches.

Next, you will make the half-open first-true formulation fully rigorous by stating its loop invariant: exactly what is known to be false, what is known to be true, and where the boundary must remain after every iteration.