Checking Predicate Monotonicity for Binary Search

Hello again. Last time, you reframed binary search as finding a boundary in a Boolean predicate over an ordered domain: typically a sequence of false values followed by true values. You also saw that exact equality is often the wrong predicate, because duplicates can create a false–true–false pattern.

This lesson sharpens the key judgment that must happen before implementation: given a proposed predicate, can its truth values support binary search? You will learn to identify the required orientation, prove monotonicity from the problem’s rules, find concise counterexamples when it fails, and repair common non-monotone formulations.

---

The formal test: what binary search is allowed to assume

Let $D$ be an ordered search domain, and let $P(x)$ be a Boolean predicate over candidates $x\in D$.

For a first-true search, the required condition is:

$$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}$$

Treating false as $0$ and true as $1$, $P$ is a nondecreasing Boolean function. Its complete sequence must have the shape

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

For a last-true search, the direct predicate has the reverse orientation:

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

Both are usable. The difference is the boundary you intend to find.

Search objective	Required predicate shape	Interpretation
First true	false values, then true values	Find the minimum qualifying candidate
Last true	true values, then false values	Find the maximum qualifying candidate

The all-false and all-true cases are valid monotone cases. There may be no transition inside the domain, but the predicate still never reverses direction.

The phrase “monotone predicate” is therefore not a vague statement that the input is somehow sorted. It is a precise promise:

Once the predicate becomes true, it cannot later become false.

That promise is what makes a midpoint informative. If $P(m)$ is true, every candidate to the right is also true, so none can be the first true candidate. If $P(m)$ is false, every candidate to the left is also false, so none can be the answer.

Without this propagation property, discarding half the domain is unjustified.

---

Monotonicity is relative to the domain and its order

A predicate is not monotone “in isolation.” It is monotone with respect to an ordered domain.

For example, suppose:

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

and the domain is the index set $0,\dots ,6$, ordered by increasing index.

The predicate

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

evaluates to:

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

It is monotone because the vector is sorted: if an element at index $i$ is at least $6$, every later element is at least as large.

But sorted input does not make every predicate over the input monotone. Consider:

$$Q(i)\equiv A[i]\text{ is even}$$

For

$$A=[1,2,3,4,5],$$

we get:

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

The indices are ordered and the values are sorted, but parity does not propagate to the right. A true result at index $1$ tells you nothing about index $2$.

This is a frequent competitive-programming mistake:

“The array is sorted, so I can binary search this condition.”

The repair is to ask a more specific question:

“If this condition is true at one index, what fact forces it to remain true at every later index?”

If there is no answer, the predicate is not suitable for first-true binary search.

The same principle applies when the domain is not an array. Candidates may be capacities, days, scores, distances, or answer values. What matters is that candidates have an order in which a constraint consistently becomes easier or consistently becomes harder.

---

A reliable monotonicity diagnosis

When someone proposes a predicate, do not begin by simulating binary-search updates. First run this short analysis.

1. State the candidates and their order

Write the domain explicitly.

Examples:

• indices $0,\dots ,n-1$, ordered left to right;
• capacities from $L$ through $R$, ordered from smaller to larger;
• days from $1$ onward, ordered chronologically;
• a sorted list of possible scores, ordered increasingly.

The order is part of the claim. A condition may be monotone in one order and non-monotone in another.

2. Choose the intended orientation

For a minimization problem, use a predicate such as:

$$P(x)\equiv \text{“candidate }x\text{ is feasible”}$$

If larger $x$ makes the constraint easier, seek the first true.

For a maximization problem, use:

$$Q(x)\equiv \text{“candidate }x\text{ is achievable”}$$

If larger $x$ makes the constraint harder, seek the last true.

You can always complement a valid true-then-false predicate:

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

This gives a false-then-true predicate. In practice, however, it is often clearer to keep the predicate expressed in the problem’s natural language and select the matching boundary template later.

3. Look for a one-directional change in constraints

The strongest monotonicity proofs come from constraint relaxation.

Suppose $P(c)$ means:

All packages can be shipped within $d$ days using capacity $c$.

As $c$ increases, the capacity constraint becomes weaker. Any schedule that works at capacity $c$ also works unchanged at capacity $c+1$. Therefore:

$$P(c)⟹P(c+1)$$

and, by repetition,

$$P(c)⟹P(c^{\prime })\text{for all }{c}^{\prime }>c$$

This is a complete proof of first-true monotonicity. Notice that it does not depend on the eventual greedy implementation of the feasibility test. Monotonicity follows directly from the meaning of “capacity at most $c$.”

4. Try to break it with a reversal

For a first-true predicate, you need only find two candidates $a<b$ such that:

$$P(a)=\text{true}\text{and}P(b)=\text{false}$$

That single pair disproves monotonicity.

For a last-true predicate, look for:

$$Q(a)=\text{false}\text{and}Q(b)=\text{true}$$

A small counterexample is usually more useful than an abstract objection: it identifies exactly what information binary search would wrongly discard.

5. Check the predicate’s exact wording

Words such as exactly, equal, odd, divisible, and contains should make you cautious. They often describe scattered valid candidates rather than a threshold.

Words such as at least, at most, no later than, within, and can accommodate often signal a monotone feasibility condition—but only after you prove how changing the candidate relaxes or tightens the requirement.

---

Worked classifications: valid, invalid, and repaired predicates

Equality in a sorted vector: invalid

Task: find whether a sorted vector contains target.

A tempting predicate is:

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

For

$$A=[1,3,3,3,5],\text{target}=3,$$

the values are:

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

This predicate changes twice. It is neither first-true nor last-true monotone.

The issue is semantic: equality describes a region of matching values, not a threshold separating the whole domain into two sides.

Repair: use a threshold predicate:

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

This is false-then-true. Find its first true position, then validate whether that position contains target.

Alternatively, to find the position after all duplicates:

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

This is also false-then-true.

---

“The event occurs on day $d$”: invalid

Suppose an event happens on exactly one day, say day $12$. Consider:

$$P(d)\equiv \text{“the event occurs on day }d\text{”}$$

Its truth values resemble:

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

A single true value in the middle is not a boundary. Discovering that the event does not occur on day $20$ tells you nothing about whether it occurred on day $10$.

Repair: change the question to a cumulative one:

$$Q(d)\equiv \text{“the event has occurred by day }d\text{”}$$

If the event is irreversible, then once $Q(d)$ is true it remains true on all later days. Now the first true day is the event day.

This repair appears constantly in scheduling and “earliest time” problems: replace an exact-time property with a “by this time” feasibility property.

---

Feasible workload cap: valid

Suppose a set of sequential jobs must be assigned to at most $k$ workers. Let:

$$P(x)\equiv \text{“the jobs can be partitioned so every worker receives workload at most }x\text{”}$$

This is first-true monotone.

Proof: If a particular partition satisfies a workload cap of $x$, the same partition also satisfies any larger cap $y>x$. Increasing the cap cannot invalidate an already valid partition.

The important detail is that the proof concerns the existence of a valid partition. You need not know which partition will be used at each value of $x$; one valid partition at $x$ is enough to establish feasibility for every larger bound.

---

Absolute value in a sorted vector: generally invalid

Suppose $A$ is sorted and you propose:

$$P(i)\equiv |A[i]|\ge 4$$

For

$$A=[-8,-3,1,6],$$

the predicate values are:

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

The absolute value decreases toward zero and then increases again. Sortedness of $A$ does not imply sortedness of $|A[i]|$.

A direct counterexample already proves this predicate cannot support an ordinary boundary search over all indices.

Possible repairs depend on the actual task:

• If the desired property is “first value at least $4$,” use $A[i]\ge 4$.
• If the task concerns absolute values, split the problem around zero, or use a different ordered candidate domain.
• If the array is known to contain only nonnegative values, then $|A[i]|=A[i]$, and the predicate becomes monotone.

The general lesson is that an operation applied to sorted values must itself preserve order before it can justify a threshold predicate.

---

Rotated sorted array with an ordinary threshold: invalid

For a rotated sorted vector,

$$A=[4,5,1,2,3],$$

consider:

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

The outcomes are:

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

There are two transitions, so the usual lower-bound predicate over the whole index range fails.

This does not mean rotated arrays are impossible to search. It means this particular predicate-domain pair is unsuitable. Later, you will use structural predicates based on which half is ordered or where the rotation boundary lies.

---

Proof patterns worth memorizing

For interview explanations and contest write-ups, a monotonicity proof is often just one or two sentences. These patterns cover much of answer-space binary search.

Candidate increases	Typical predicate	Proof idea	Orientation
Capacity	Can all items fit?	More capacity relaxes a limit.	First true
Deadline	Can all work finish by then?	More time allows every earlier schedule.	First true
Processing speed	Can all work finish by deadline?	More speed cannot require more time.	First true
Minimum separation	Can at least $k$ items be placed?	More required distance makes placement harder.	Last true
Target score	Is this score achievable?	A higher target is at least as demanding.	Last true
Allowed error	Is approximation acceptable?	Larger tolerance relaxes acceptance.	First true

Be precise about direction. “The predicate is monotone” is incomplete unless you indicate which way it moves.

For example, with a minimum-distance placement problem, let:

$$P(d)\equiv \text{“it is possible to place at least }k\text{ items pairwise at distance at least }d\text{”}$$

If $P(d)$ is true, then every smaller separation requirement is also true. Thus the pattern is true-then-false, and you seek the last true distance.

A common error is to use the correct feasibility function but reason in the wrong direction. State the implication explicitly:

$$P(d)⟹P(d-1)$$

That one line exposes the correct orientation.

---

Sampling helps debugging, but it is not a proof

For a small example, writing a truth table is an excellent sanity check. It quickly reveals patterns like:

$$[F,T,F]$$

or

$$[T,F,T]$$

which are immediate disqualifiers.

But sampled values cannot prove monotonicity over a large domain. A predicate may look monotone at the endpoints and midpoint while reversing in between. For example:

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

could appear harmless if you sampled only the first, middle, and last positions poorly.

Use two levels of validation:

1. Semantic proof: explain why a true candidate stays true as candidates increase, or why a true candidate stays true as candidates decrease.
2. Small-instance testing: enumerate candidate values for tiny random cases and inspect the resulting Boolean sequence.

The proof establishes correctness. Small tests catch an incorrect implementation of a predicate whose intended logic was monotone.

Also separate two concerns:

• Monotonicity: does binary search have the right to discard half the candidate space?
• Predicate correctness and cost: does your feasible(x) function return the right answer quickly enough?

A perfectly monotone predicate that costs too much may still be impractical. A fast predicate that is not monotone cannot safely be binary-searched at all.

---

Key takeaways

Binary search requires a Boolean predicate whose values make at most one directional transition over a clearly ordered domain.

• For first true, prove that true persists to the right.
• For last true, prove that true persists to the left.
• A sorted input does not automatically make an arbitrary condition over its indices monotone.
• Equality and “exactly” conditions are often non-monotone; threshold or cumulative formulations frequently repair them.
• The most convincing monotonicity proofs come from showing that increasing a candidate consistently relaxes, or consistently tightens, the problem’s constraints.
• A single reversal is enough to reject a proposed predicate.

Next, you will turn a valid first-true formulation into a precise search contract, choosing between inclusive and half-open intervals while preserving correct behavior for all-true, all-false, and empty domains.