Binary Search
& Answer Space
Applying monotonic logic to efficiently narrow down search spaces.
What This Pattern Is Really About
Binary search is not about finding an element; it is about discarding half the search space. Every decision permanently eliminates a range of impossible candidates.
It is a mechanism to convert a search problem into a series of Yes/No questions. If you can define a monotonic predicate, you can search anything.
In arrays, indices represent the search space. The sorted property guarantees that checking a midpoint validates or invalidates an entire half.
Often the answer is not in an array but in a range of values (e.g., time, capacity). If the validity function is monotonic, the answer itself can be binary searched.
Mental Model & Invariant
Search domains must be ordered. If index i satisfies a condition, then either all indices >i or all indices <i must also satisfy (or fail) that condition.
This monotonicity allows checking a single midpoint to make a valid claim about half the entire domain.
Every update to low or high must preserve this truth.
Monotonic Feasibility
The predicate function (isValid, isPossible) must switch from False to True (or vice-versa) exactly once across the domain.
Search Space Definition
Whether array indices [0, n-1] or numerical range [min, max], the boundaries must cover all possible valid answers.
When to Think "Binary Search"
network_checkStrong Signals
Input array is already sorted
Searching for a value in a monotonic range
Finding the first or last occurrence of a value
Accessing index is O(1) random access
Maximizing or minimizing a value constrained by a function
timerConstraint Signals
O(log N) time complexity required
N is large (e.g., 10^5 or greater)
Input too large to iterate linearly
Memory limit prevents auxiliary data structures
Simple linear scan results in Time Limit Exceeded
Binary Search Variants You Must Master
Classic Binary Search
Find exact index of target in sorted array.
"Target is in [low, high] if it exists."
Lookup existence or index.
First / Last Occurrence
Find boundaries of duplicate elements.
"All values < target are left; all > target are right."
Counting frequencies or range boundaries.
Answer Space Search
Find min/max value satisfying a condition.
"Range [L, R] contains the optimal valid answer."
Optimization problems where answer is monotonic.
Capacity / Allocation
Determine min capacity to handle workload.
"If capacity K works, K+1 works too."
Load balancing, shipping, cutting items.
Search on Real Numbers
Find root or value with decimal precision.
"Root lies within [L, R] error margin."
Geometry, physics, or continuous mathematical functions.
How to Learn Binary Search Properly
Identify Monotonicity
Before searching, define the property that allows elimination. Is the array sorted? Does the answer space go from False -> True?
Define the Feasibility Function
Isolate the logic that checks a single candidate value. Create a `check(x)` function that returns a boolean.
Establish the Invariant
Decide whether your answer is in [L, R] or (L, R]. Stick to one convention for all problems to build muscle memory.
Handle Termination & Boundaries
Determine if the loop ends when L == R or L > R. Verify strict inequalities to prevent infinite loops.
Trace Edge Cases Manually
Walk through arrays of size 0, 1, and 2. Ensure your termination logic holds without off-by-one errors.
Canonical Problem List
folder_openFoundation — Classic Search
Binary Search
Implementation of the basic algorithm on a sorted array.
Search Insert Position
Standard search, but returning the potential index on failure.
Peak Index in Mountain Array
Finding a peak in bitonic data (increasing then decreasing).
Sqrt(x)
Applying binary search on the number line integer space.
Search in Rotated Sorted Array
Handling a meaningful disruption in sorting order.
folder_openIntermediate — Boundary Search
First / Last Position of Element
Finding the edges of a range of duplicates.
First Bad Version
Classic problem of finding the first true in a monotonic boolean sequence.
Find Minimum in Rotated Array
Identifying the pivot point where order resets.
H-Index II
Searching for a condition where index meets value properties.
folder_openIntermediate — Answer Space
Koko Eating Bananas
Minimizing a rate k such that a task completes in time h.
Capacity To Ship Packages
Finding minimum capacity to ship items within d days.
Minimum Number of Days to Make m Bouquets
Monotonic search on time to satisfy allocation constraint.
Minimized Maximum of Products Distributed
Classic min-max allocation problem.
folder_openAdvanced — Monotonic Optimization
Split Array Largest Sum
Similar to shipping/capacity, partitioning array to minimize max sum.
Aggressive Cows
Maximizing the minimum distance between placed elements.
Median of Two Sorted Arrays
Binary search on partition points of two arrays simultaneously.
K-th Smallest Number in Multiplication Table
Search on value space to count elements smaller than mid.
Solving hundreds of problems isn't necessary. These cover the distinctive monotonic patterns; others are just flavor text on the same logic.
Common Mistakes
Infinite Loops (mid selection)
Left-biased mid `(L+R)/2` combined with `L = mid` causes infinite loops on 2-element arrays.
Use `mid = (L+R+1)/2` for right-bias if updating `L = mid`.
Integer Overflow
Calculating `(L+R)/2` exceeds max integer limit when indices are large.
Use `L + (R-L)/2` to prevent overflow.
Off-by-One (L < R vs L <= R)
Mismatched loop condition and update logic leaves one element unchecked or causes infinite loop.
If update excludes mid (`L=mid+1`), use `L <= R`. If update keeps mid (`R=mid`), use `L < R`.
Applying to Unsorted Data
No monotonic property exists, so elimination logic is invalid.
Sort the data first or verify a rotated/mountain property exists.
Premature Optimization of Range
Trying to tighten [L, R] bounds manually often misses valid answers.
Start with a safe, wide range (e.g., [0, max_val]) and let the algorithm narrow it.
Interview Guidance
What they test
- →Boundary correctness (L < R vs L ≤ R)
- →Identifying hidden monotonicity
- →Handling integer overflow
- →Defining search space accurately
The Insight
The key isn't writing the loop—it's proving the problem is monotonic. If you can explain why `check(x)` allows you to discard half the universe, the implementation is just a formality.
The Verbal Template
"The answer lies between [min_possible, max_possible]."
"The `check(x)` function is monotonic: if X works, all values >X (or <X) also work."
"Therefore, I'll test `mid`. If `check(mid)` is true, I can safely discard the [left/right] half."
"This reduces the search space logarithmically to find the boundary."
When You've Mastered This Pattern
Can define search space instantly
Writes L <= R or L < R without guessing
Spots monotonicity in 'unsorted' problems
Never writes infinite loops
Applies to non-integer domains (time, real numbers)
Explains 'why' before writing 'while'
What This Unlocks Next
Segment Trees
Binary search applied to range query data structures.
Two Pointers
Linear elimination logic often combined with binary search.
Newton's Method
Faster convergence on continuous functions using derivatives.
Ternary Search
Finding optima in unimodal functions by dividing into three parts.
"If you can define a monotonic Yes/No question, you can find the answer in logarithmic time. That is a superpower."