Formulating Boundary-Finding Problems as Boolean Predicates

Hello, and welcome to a course about binary search as a reasoning tool, not merely a familiar loop over a sorted vector. Over the course, you will move from precise boundary contracts and correctness arguments to answer-space searches, feasibility checks, implicit domains, and harder competitive-programming patterns.

The central shift begins here: binary search does not fundamentally search for a value. It finds a boundary in an ordered set of candidates. To use it reliably, first turn the problem into a yes/no question whose answers change in only one direction.

By the end of this lesson, you should be able to take a boundary-finding task, state its ordered search domain, define a Boolean predicate over that domain, and express the desired result as the first or last point at which that predicate holds.

---

From “find an element” to “find a transition”

Consider a sorted vector:

$$A=[1,3,3,5,8,8,12]$$

Suppose the task is:

Find the first index whose value is at least $8$.

A direct description is “find the first $8$.” But that wording is too narrow: if $8$ did not occur, the meaningful answer would still be the index where $8$ could be inserted while preserving sorted order.

Instead, define a predicate over indices:

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

Evaluating it at every index gives:

Index $i$	0	1	2	3	4	5	6
$A[i]$	1	3	3	5	8	8	12
$P(i)$	F	F	F	F	T	T	T

The actual problem is now:

Find the first true position.

That boundary is index $4$. The target value happens to occur there, but the predicate formulation also works when it does not.

For target $6$, the same predicate,

$$P(i)\equiv A[i]\ge 6,$$

produces:

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

The first true index is again $4$, which is precisely the insertion position of $6$.

This is the abstraction to keep:

1. Identify a set of candidate answers.
2. Put those candidates in an order.
3. Ask one yes/no question about each candidate.
4. Find the point at which answers switch from one truth value to the other.

The binary-search loop comes after this modeling work.

---

The required shape: monotonicity

For the canonical “first true” formulation, predicate values must have this shape:

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

Formally, if the ordered domain is $D$, the predicate must be monotone nondecreasing:

$$x<y\text{ and }P(x)=\text{true}⟹P(y)=\text{true}$$

Equivalently:

$$x<y\text{ and }P(y)=\text{false}⟹P(x)=\text{false}$$

A true answer certifies every later candidate as true; a false answer certifies every earlier candidate as false. Those are exactly the facts that let binary search discard half the domain safely.

There are two usable orientations:

Desired boundary	Predicate pattern	Typical statement
First true	$F\dots F,T\dots T$	First index with $A[i]\ge x$
Last true	$T\dots T,F\dots F$	Last index with $A[i]\le x$

The two are not fundamentally different. If $Q(i)$ has the true-then-false pattern, then its complement

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

has the false-then-true pattern. You can then search for the first true of $P$, which lies immediately after the last true of $Q$.

For now, make first true your default mental model. It is especially natural for minimums, insertion positions, and “at least” constraints.

---

State the domain before defining the predicate

A predicate alone is not enough. It must be defined over an ordered domain of candidate answers.

In the sorted-vector example:

• Domain: indices $0,1,\dots ,n-1$
• Order: ordinary increasing index order
• Predicate: $P(i)\equiv A[i]\ge \text{target}$
• Boundary sought: first $i$ for which $P(i)$ is true

This four-part statement is a compact problem specification. It also stops a common error: using a predicate over the wrong thing.

Example: threshold in a sorted vector

Task:

Find the first value at least target.

Correct formulation:

$$D=\{0,1,\dots ,n-1\}$$ $$P(i)\equiv A[i]\ge \text{target}$$

Find the first true index.

Why is it monotone? Because $A$ is sorted. If $A[i]\ge \text{target}$, every later value is at least $A[i]$, hence also at least target.

Example: first element strictly greater than a target

Task:

Find the first element greater than target.

Only the predicate changes:

$$P(i)\equiv A[i]>\text{target}$$

This is still false followed by true. For

$$A=[2,4,4,4,7],\text{target}=4,$$

the values of $P$ are:

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

The first true is index $4$. This is the conceptual meaning of upper_bound.

Example: last element at most a target

Task:

Find the last index $i$ satisfying $A[i]\le \text{target}$.

The direct predicate is:

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

Its shape is:

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

That is a valid one-transition pattern, but it is the reverse orientation. A first-true equivalent is:

$$P(i)\equiv A[i]>\text{target}$$

Find the first true index $b$; then the last index at most the target is $b-1$.

This “find the first violation, then step back” transformation will be useful throughout the course.

---

Exact search is often a boundary problem in disguise

A conventional exact-match predicate looks like this:

$$E(i)\equiv A[i]=\text{target}$$

For a sorted vector with duplicates, its truth values may look like:

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

That is not monotone: it changes from false to true and then back to false. A boundary search cannot safely use $E$ directly.

The repair is to search for a monotone threshold predicate instead:

$$P(i)\equiv A[i]\ge \text{target}$$

Find its first true index $b$. Then perform one final validation:

• If $b<n$ and $A[b]=\text{target}$, then $b$ is the first occurrence.
• Otherwise, the target is absent.

So even an “exact search” can be decomposed into:

1. Find the lower boundary.
2. Check whether the boundary element equals the target.

This is more general than returning immediately on equality, because it handles duplicates and naturally yields an insertion position when the target is absent.

---

Boundary contracts and the edge cases

For a finite index domain $0,\dots ,n-1$, define the boundary as:

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

when a true index exists.

But a robust contract must say what happens when no true index exists. The cleanest mathematical convention is to allow the boundary to be one past the vector:

$$b\in [0,n]$$

with:

• $b=0$ if every position is true;
• $b=n$ if every position is false;
• otherwise, $b$ is the first true index.

For a sorted vector and

$$P(i)\equiv A[i]\ge \text{target},$$

this gives the full insertion-position contract:

Situation	Predicate pattern	Boundary
Target is no larger than every element	all true	$0$
Target belongs between existing values	false then true	first qualifying index
Target is larger than every element	all false	$n$
Vector is empty	no positions	$0=n$

Notice that “all false” is not a failure of the method. It represents a legitimate boundary after the domain. Likewise, “all true” places the boundary before or at the first element.

At this stage, do not worry about which C++ loop variables represent this contract. The next lessons will derive half-open and sentinel-based implementations precisely. What matters today is that the problem contract is settled before any updates or midpoint calculations are written.

---

Beyond arrays: candidates can be possible answers

The domain does not need to be array indices. It can be any ordered collection of candidates.

Suppose a problem asks:

What is the minimum integer capacity $c$ that lets a set of packages be shipped within $d$ days?

The candidate answers are capacities, perhaps from the heaviest package weight up to the sum of all weights. Define:

$$P(c)\equiv \text{“capacity }c\text{ permits shipping all packages within }d\text{ days”}$$

We seek the first true capacity.

Why is $P$ monotone? If capacity $c$ is sufficient, every capacity larger than $c$ is also sufficient: extra capacity cannot make a feasible schedule infeasible.

This is a reduction from an optimization problem to a decision problem:

Original wording	Predicate wording
Minimize the capacity	Is capacity $c$ sufficient?
Maximize an achievable score	Is score $s$ achievable?
Find the earliest acceptable day	Is day $d$ late enough?

The question “is this candidate sufficient?” is frequently easier to answer than “what is the optimum?” Once its answers are monotone, the optimum is a boundary.

A useful discipline is to write the predicate as a complete English sentence before turning it into code. For example:

“There exists a schedule that finishes all jobs by time $t$.”

That sentence makes the direction of monotonicity visible: increasing $t$ relaxes the deadline, so a true result remains true.

---

A predicate-design checklist

Before implementing any binary search, write down these five lines on paper or in a code comment:

1. Candidate domain: What values could the answer be?
2. Order: In what increasing order are candidates arranged?
3. Predicate: What exactly does $P(x)$ mean?
4. Boundary: Do I seek the first true or the last true?
5. Monotonicity proof: Why can the predicate change at most once?

For a lower bound, that becomes:

Domain: indices $0$ through $n-1$.
Order: increasing index.
Predicate: $P(i)$ means $A[i]\ge \text{target}$.
Boundary: first true, with $n$ if none exists.
Proof: sortedness means every later array value is at least as large.

For a minimum feasible capacity problem:

Domain: feasible integer capacity range.
Order: increasing capacity.
Predicate: $P(c)$ means all work can be completed with capacity $c$.
Boundary: first true.
Proof: a larger capacity only relaxes constraints.

If you cannot write a convincing monotonicity sentence, do not start coding binary search. Either the predicate is wrong, the domain order is wrong, or the problem needs another technique.

---

Key takeaways

Binary search is best understood as a search for a transition in a Boolean predicate over an ordered domain.

• A canonical first-true predicate has the form $F\dots F,T\dots T$.
• The domain may be indices, times, capacities, scores, or another ordered set of candidate answers.
• Equality is often non-monotone; replace it with a threshold predicate such as $A[i]\ge x$, then validate the resulting boundary if exact presence matters.
• A complete formulation states the domain, predicate, boundary, edge-case behavior, and a short monotonicity argument.
• All-true and all-false predicate values are normal cases, not exceptional failures.

Next, you will focus on recognizing whether a proposed predicate is genuinely monotone—and on repairing tempting predicates that are not.