7.5 Monotone Predicates

Binary search does not fundamentally require sorted data.

What binary search actually requires is a monotone predicate.

This observation is one of the most important ideas in algorithm design because it explains why binary search appears in problems involving scheduling, optimization, geometry, networking, manufacturing, databases, and machine learning despite the absence of a sorted array.

Once you learn to identify monotone predicates, binary search becomes a general-purpose boundary-finding technique rather than a search algorithm for arrays.

Problem

You need to determine whether binary search can be applied to a problem.

The challenge is identifying whether the problem contains a monotone structure.

Consider a sequence of values:

1 2 3 4 5 6 7 8 9

Suppose we define:

x >= 6

Evaluating the condition produces:

F F F F F T T T T

The result changes exactly once.

Binary search can locate this transition.

Now consider:

x is even

Evaluating:

F T F T F T F T F

The condition changes repeatedly.

Binary search cannot be applied.

Understanding the difference is essential.

What Is a Monotone Predicate?

A predicate is a function that returns either true or false.

func Predicate(x int) bool

A predicate is monotone if the truth value changes at most once across an ordered search space.

Common forms include:

False False False True True True

True True True False False False

Both contain a single transition.

Binary search can efficiently locate that boundary.

Non-monotone predicates contain multiple transitions.

False True False True False

Such predicates do not satisfy binary search requirements.

Visualizing the Boundary

Consider:

Capacity: 1 2 3 4 5 6 7 8

Suppose a server can handle a workload only when capacity reaches at least five.

Results:

F F F F T T T T

Graphically:

Capacity
1 2 3 4 5 6 7 8
        ^
      boundary

Binary search does not care about the meaning of capacity.

It only cares that the boundary exists.

This separation between domain meaning and search structure is what makes binary search broadly applicable.

Example: Download Speed

Suppose a file must be downloaded within one hour.

Possible network speeds:

1 MB/s
2 MB/s
3 MB/s
...

Define:

Can finish within one hour?

Results:

F F F F T T T T

The first true value corresponds to the minimum acceptable speed.

The actual domain happens to be networking, but the algorithm sees only a monotone predicate.

Example: Machine Production

A factory machine produces parts.

You need at least:

10,000 units

within a week.

Define:

Can machine speed S produce
10,000 units within a week?

Possible results:

F F F F F T T T T

Again, a single transition exists.

Binary search applies immediately.

Example: Exam Scores

Suppose grades are sorted.

32 45 51 58 67 71 84 92

Define:

score >= 60

Results:

F F F F T T T T

The first true value identifies the first passing score.

This is exactly a lower-bound search.

Monotonicity in Geometry

Geometry problems often contain hidden monotone predicates.

Suppose you need the smallest radius that covers all points.

Define:

Can radius R cover all points?

Results:

F F F F T T T T

If a radius works, every larger radius also works.

That property creates monotonicity.

Binary search can therefore search the radius.

Many computational geometry optimization problems rely on this idea.

Monotonicity in Scheduling

Suppose jobs must complete within:

30 minutes

Define:

Can N workers complete all jobs
within 30 minutes?

Results:

F F F T T T T T

If five workers can complete the work, six workers can as well.

Feasibility grows monotonically.

The worker count can be searched.

This pattern appears repeatedly in resource allocation systems.

Monotonicity in Databases

Consider a sorted index:

Define:

value >= 200

Results:

F F F T T T

This monotone structure is the reason lower-bound and upper-bound searches work.

Database indexes depend heavily on this property.

B-trees, skip lists, and many storage engines are optimized around locating these boundaries.

Detecting Monotonicity

When facing a new problem, ask:

Is there an ordered search space?
Can I evaluate a candidate solution?
Once the predicate becomes true, does it stay true?
Once the predicate becomes false, does it stay false?

If the answer is yes, binary search is usually possible.

For example:

Can complete within X days?

Often monotone.

Can fit into Y containers?

Often monotone.

Can process using Z memory?

Often monotone.

These questions naturally produce boundaries.

Building Feasibility Functions

Most search-on-answer problems consist of two parts.

The search:

for lo < hi {
	mid := lo + (hi-lo)/2

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

And the predicate:

func feasible(x int) bool {
	// verify candidate answer
}

The predicate is usually the difficult part.

The binary search itself is often identical across problems.

Experienced algorithm designers spend most of their effort constructing an efficient monotone feasibility function.

Common Non-Monotone Traps

Not every optimization problem can be transformed into binary search.

Consider:

Profit generated by price P

Results might look like:

10 15 22 30 28 21 14

Profit increases and then decreases.

There is no single transition.

Binary search cannot directly locate the optimum.

Another example:

Randomized success rates

Results:

F T F T T F

The predicate changes multiple times.

Binary search assumptions are violated.

Whenever multiple transitions appear, binary search becomes unsafe.

Formal View

Let a predicate be:

P(x)

Binary search applies when there exists a boundary value b such that:

x < b  => P(x) = false
x ≥ b  => P(x) = true

or the reverse:

x < b  => P(x) = true
x ≥ b  => P(x) = false

The entire algorithm exists to discover b.

Everything else is implementation detail.

Complexity Benefits

Suppose a search space contains:

1,000,000 values

Linear search requires:

O(n)

evaluations.

Binary search requires approximately:

log₂(1,000,000) ≈ 20

evaluations.

Reducing one million checks to twenty is the reason monotone predicates are so valuable.

The search becomes dramatically more efficient once a boundary can be identified.

Common Mistakes

Many developers discover a feasibility function and immediately apply binary search without proving monotonicity.

A few successful test cases may hide subtle violations.

Always verify that the predicate changes at most once across the search space.

Another mistake is constructing a predicate whose result depends on mutable global state. Binary search assumes consistent answers for repeated evaluations. Side effects break that assumption.

A third mistake is choosing an incorrect search domain. Even a perfectly monotone predicate becomes useless if the search interval does not contain the actual boundary.

Takeaway

Monotone predicates are the true foundation of binary search. Arrays, sorted lists, capacities, distances, timestamps, machine speeds, worker counts, and geometric measurements are merely different domains that produce the same underlying structure: a single transition between false and true. Once you learn to identify that transition and express it as a feasibility function, a wide range of optimization and search problems become candidates for logarithmic-time solutions.