Binary Search Pattern
Binary Search Is About a Boundary, Not an Array
Most people learn binary search as "find a value in a sorted array". The more useful view: binary search finds the boundary in any yes/no question whose answers switch from "no" to "yes" exactly once.
ok(x): F F F F F T T T T
x: 0 1 2 3 4 5 6 7 8
↑
the first T — this is what we search for
Each check at the middle discards half of the remaining range.
A range of 1,000,000 candidates needs only about 20 checks.
The Binary Search page covers the algorithm itself, and Binary Search Patterns works through many classic problems. This page focuses on recognising binary search and solving every variant with one template.
The One Template
first_true(lo, hi, ok): # answer lies in [lo, hi]; hi means "none"
while lo < hi:
mid = lo + (hi - lo) / 2 # avoids overflow of lo + hi
if ok(mid):
hi = mid # mid may be the answer → keep it
else:
lo = mid + 1 # mid is not the answer → drop it
return lo # lo == hi == first true
Loop ends when lo == hi. No "is it found?" check inside,
no off-by-one decisions per problem. Only ok() changes.
Every variant below is just a different ok.
Variant 1: Boundaries in Sorted Data
temps (sorted): [11, 14, 14, 14, 19, 23, 23, 30] index: 0 1 2 3 4 5 6 7 first index with value ≥ 14 → ok(i) = temps[i] ≥ 14 → 1 first index with value > 14 → ok(i) = temps[i] > 14 → 4 count of 14 = 4 − 1 = 3 value 20 (absent): ≥ gives 5, > gives 5 → count 0, and 5 is where 20 would be inserted to keep the list sorted.
These two boundaries (often called lower bound and upper bound) answer: count of a value, insert position, closest value, values within a range [a, b] (= first > b − first ≥ a).
Variant 2: Searching Over the Answer
The answer is a number in a known range, and you can check whether a candidate is good enough. If "good enough" is monotone, binary search the candidates.
Batches arrive in a fixed order: [4, 8, 2, 7, 3, 6, 5] Each day you process consecutive batches up to a daily CAPACITY. What is the smallest capacity that finishes within D days? Candidate range: lo = max(batches) = 8 (any less and the 8 can never be processed) hi = sum(batches) = 35 (one day does everything) ok(cap) = days_needed(cap) ≤ D ← greedy simulation, O(n) Monotone: more capacity never needs MORE days. D = 3: cap 21 → 2 days ✓ hi = 21 cap 14 → 3 days ✓ hi = 14 cap 11 → 4 days ✗ lo = 12 cap 13 → 3 days ✓ hi = 13 cap 12 → 3 days ✓ hi = 12 (lo == hi → stop) cap 12 is the answer: [4, 8] [2, 7, 3] [6, 5]
Wording that signals this variant: "minimum largest …", "maximum smallest …", "least speed / capacity / time such that …".
Variant 3: Math Functions
Integer square root of n = largest r with r² ≤ n = (first r with r² > n) − 1 isqrt(15) = 3, isqrt(16) = 4
Variant 4: Real Numbers
Cube root of 50 to 4 decimal places:
lo = 0, hi = 50
repeat 100 times:
mid = (lo + hi) / 2
if mid³ < 50: lo = mid else: hi = mid
→ 3.6840
No "+1": on real numbers there is no "next" value. Use a fixed
iteration count (or stop when hi − lo < tolerance).
Code: One Template, Four Variants
import java.util.function.LongPredicate;
public class BinarySearchPattern {
// Smallest x in [lo, hi] with ok(x) true (ok must be F...F T...T)
static long firstTrue(long lo, long hi, LongPredicate ok) {
while (lo < hi) {
long mid = lo + (hi - lo) / 2;
if (ok.test(mid)) hi = mid; // mid might be the answer — keep it
else lo = mid + 1; // mid is definitely not the answer
}
return lo;
}
// Boundaries in a sorted array
static int firstAtLeast(int[] a, int x) { return (int) firstTrue(0, a.length, i -> a[(int) i] >= x); }
static int firstGreater(int[] a, int x) { return (int) firstTrue(0, a.length, i -> a[(int) i] > x); }
// Search on the answer: smallest daily capacity finishing all batches within `days`
static int daysNeeded(int[] batches, long cap) {
int days = 1;
long load = 0;
for (int b : batches) {
if (load + b > cap) { days++; load = 0; }
load += b;
}
return days;
}
static long minCapacity(int[] batches, int days) {
long lo = 0, hi = 0;
for (int b : batches) { lo = Math.max(lo, b); hi += b; }
return firstTrue(lo, hi, cap -> daysNeeded(batches, cap) <= days);
}
// Integer square root: (first r with r*r > n) - 1
static long isqrt(long n) { return firstTrue(0, n + 1, r -> r * r > n) - 1; }
// Real-valued search: a fixed number of halvings
static double cubeRoot(double x) {
double lo = 0, hi = Math.max(1.0, x);
for (int it = 0; it < 100; it++) {
double mid = (lo + hi) / 2;
if (mid * mid * mid < x) lo = mid; else hi = mid;
}
return lo;
}
public static void main(String[] args) {
int[] temps = {11, 14, 14, 14, 19, 23, 23, 30};
for (int x : new int[]{14, 20, 31}) {
int lo = firstAtLeast(temps, x), hi = firstGreater(temps, x);
System.out.println(x + ": first >= at " + lo + ", first > at " + hi + ", occurrences " + (hi - lo));
}
int[] batches = {4, 8, 2, 7, 3, 6, 5};
for (int d : new int[]{1, 3, 7})
System.out.println("min capacity for " + d + " day(s): " + minCapacity(batches, d));
System.out.println("isqrt: " + isqrt(0) + " " + isqrt(15) + " " + isqrt(16) + " " + isqrt(1000000));
System.out.println(String.format("cube root of 50: %.4f", cubeRoot(50)));
}
}Output:
14: first >= at 1, first > at 4, occurrences 3
20: first >= at 5, first > at 5, occurrences 0
31: first >= at 8, first > at 8, occurrences 0
min capacity for 1 day(s): 35
min capacity for 3 day(s): 12
min capacity for 7 day(s): 8
isqrt: 0 3 4 1000
cube root of 50: 3.6840
How to Spot Binary Search in Disguise
✓ Sorted input + "find / count / first / last / insert position"
✓ "Minimum X such that ..." or "maximum X such that ..."
→ is "X works" monotone? → search over X
✓ n or values up to 10^9 / 10^18 → a linear scan of candidates is impossible
✓ An expensive yes/no check that's easy to write, but no formula for the answer
✓ Rotated or "mountain" arrays — one half is always sorted / monotone
The test: write ok(x) in words. If you can argue "if ok(x) is true then ok(x+1) is true", binary search applies.
Choosing the Search Range
lo must be a value that is definitely ≤ the answer hi must be a value that is definitely ≥ the answer (or "not found") Capacity / speed / time problems: lo = the largest single item (smaller can never work) hi = the total (one step does everything) Index searches: lo = 0, hi = n (n means "no element satisfies ok")
A range that is too narrow silently returns a wrong answer; too wide only costs a few extra iterations. When unsure, go wider.
Complexity
| Variant | Time | Space |
|---|---|---|
| Boundary in sorted array | O(log n) | O(1) |
| Search on answer | O(log(range) × cost of ok) | O(1) + ok's space |
| Integer root | O(log n) | O(1) |
| Real-valued | O(iterations) — e.g. 100 | O(1) |
For the capacity problem: O(n · log(sum)) — tiny even for sums near 10¹⁴.
Common Mistakes
Non-monotone predicate. Binary search on "is mid a peak?" or "does mid equal the target?" (when duplicates or unsorted data are involved) gives wrong answers. Rephrase as a monotone question.
hi = mid − 1 with while lo < hi. Mixing templates causes infinite loops or skipped answers. Stick to one template.
Overflow in (lo + hi) / 2. Use lo + (hi − lo) / 2, and 64-bit types when mid * mid or sums can exceed 2³¹.
while lo <= hi on real numbers. Floating-point ranges may never collapse to equality. Use a fixed iteration count.
Wrong lower bound for search-on-answer. Starting at 1 instead of max(batches) still works but the predicate must then handle impossible capacities; starting too high skips the true answer.
Interview Questions
Q: How do you decide whether to binary search over the answer?
Check whether the problem asks for the smallest (or largest) value satisfying a condition, and whether the condition is monotone in that value — if a capacity of c works, does c + 1 also work? If yes, and you can check a candidate efficiently, binary search the value range with that check as the predicate.
Q: Derive the count of values in [a, b] in a sorted array.
The first index with value > b marks the end of the range, and the first index with value ≥ a marks its start. Their difference is the count, using two O(log n) searches.
Q: Why does the template return a correct answer even when no element satisfies ok?
The range is [lo, hi] where hi itself means "none". If ok is false everywhere, every check sets lo = mid + 1 until lo reaches hi, and the caller recognises hi (e.g. n) as "not found".
Summary
- ›Binary search finds the boundary where a monotone yes/no answer flips.
- ›One template —
hi = midon true,lo = mid + 1on false — covers all integer variants. - ›Sorted data: lower bound (≥), upper bound (>), counts, insert positions.
- ›Search on answer: "minimum X such that…" with a greedy check → O(n log range).
- ›Reals: fixed iteration count, no ±1.
Next, Greedy Pattern looks at problems where the locally best choice is provably the globally best one — and how to tell when it isn't.
What property must a predicate ok(x) have for 'find the first x where ok(x) is true' to work with binary search?