0
lo
Binary search isn't just looking up a value in a sorted array — the real skill is spotting a monotone predicate hidden in the problem and searching on the answer spaceinstead of an index. When you can ask “is X feasible?” and the answer flips exactly once from false to true, you can binary-search it in O(log n).
The real subject of binary search is not a sorted array — it is a monotone yes/no question. If “is X feasible?” flips from no…no…yes…yes exactly once as X grows, you can bisect straight to the boundary in O(log n), throwing away the half that provablycan't hold the answer at every step.
Forget “look up a number in a sorted list” — that's one special case. The general picture is a line of yes/no answers that is sorted by truth: F F F F | T T T. There is exactly one seam where false becomes true, and binary search is just a fast way to find that seam.
Each probe asks the question at the midpoint. The answer doesn't just give you one data point — because the line is monotone, it tells you which entire half the seam cannot be in, so you delete that half. A sorted array is simply the case where the question is arr[i] ≥ target.
p(x)is this problem really about, and where does it first turn true?”Classic search first. Watch lo, mid, hi squeeze in, and watch a whole half vanish on every probe:
looking for 23 in a sorted array
idx : 0 1 2 3 4 5 6 7
val : [ 3 ][ 9 ][12 ][17 ][23 ][28 ][41 ][55]
lo mid hi arr[mid]=17 < 23 → go RIGHT
lo mid hi arr[mid]=41 > 23 → go LEFT
lo,hi arr[mid]=23 ✓ found, idx 4
^^^^^^^^^^^^^^^^^^^^ half thrown away EACH probe
provably can't hold 23 → never looked at again
3 probes, not 8. Each guess deletes a provable-empty half.Now the same loop with no array at all. For Koko eating bananas the “array” is the line of speeds, and the comparison is the feasibility question. We binary-search the F | T boundary:
Koko: smallest eating speed k that finishes the bananas in time.
p(k) = "can Koko finish at speed k?" (monotone: slow=no, fast=yes)
speed k : 1 2 3 4 5 6 7 8
p(k) : F F F F T T T T
↑ ↑
| └── first TRUE ← THIS is the answer
└─────── last FALSE
There is no array. We INVENT the index line [1 .. max(pile)]
and binary-search it for the F|T boundary, calling p(mid) as the
"comparison". Same loop, the array is imaginary.When a problem smells like “find the best/smallest/largest X” and brute force would just try every X, climb these rungs before writing a loop:
p(k) = can we finish at speed k?” The answer you want is a boundary between no and yes.p(x) is true, is it still true for every larger x (a bigger speed, more capacity, more days)? If yes, p goes false → true exactly once. No single flip → no binary search.lo = smallest candidate that could be the answer, hi= a value you know is feasible. Ask “what unitare these in?” — indices, or speeds/capacities (the answer space)?p(mid), keep the half that still contains the seam. The boundary is your answer.Almost all binary-search anxiety is off-by-one panic: ≤ or <? mid or mid+1? Cure it by stating one invariant out loud and never breaking it: the answer, if it exists, is always inside [lo, hi]. Every boundary update is then forced:
INVARIANT: the answer, if it exists, is always inside [lo, hi].
every line below must keep that promise.
mid ruled OUT → move the boundary PAST mid (lo = mid+1 / hi = mid-1)
mid might be IT → KEEP mid in the window (hi = mid)
found-it template lower_bound template
while (lo <= hi) while (lo < hi)
== → return mid p(mid) true → hi = mid (keep mid)
< → lo = mid+1 p(mid) false → lo = mid+1 (drop mid)
> → hi = mid-1
closed [lo,hi], empties half-open, collapses to the
when lo > hi single first-true positionmid is ruled out, move the boundary past it (lo = mid+1 or hi = mid-1) — it can never be the answer, so dropping it keeps the invariant.mid might be it, you must keep it: hi = mid. Writing hi = mid - 1 here would throw away the very answer.mid = lo + (hi - lo) / 2 → it's the same midpoint as (lo + hi) / 2 but can't overflow, and it rounds down — so in the lower_bound template mid never equals hi, which is exactly what stops the two-element infinite loop.You don't need four memorized templates — you need one and the discipline to phrase the question as a predicate. Read this as a sentence: while more than one candidate survives, probe the middle and keep the half holding the seam.
find_first_true(lo, hi): # search for the F|T boundary
# invariant: answer in [lo, hi]
while lo < hi: # window still has >1 candidate
mid = lo + (hi - lo) / 2 # midpoint, no overflow
if p(mid): # mid satisfies the predicate
hi = mid # → mid might be the answer, KEEP it
else: # mid fails
lo = mid + 1 # → answer is strictly to the right
return lo # lo == hi: the one surviving candidateThe plain “found-it” template (lo ≤ hi, return on equality) is the special case where the predicate is arr[i] === target and you can stop early. The lower_bound shape above is the one that alwaysworks — exact match, first/last position, and binary-search-on-answer all collapse into “find the first x where p(x)is true.”
Binary search silently returns garbage the moment the predicate stops being monotone. The whole trick rests on one promise: once true, always true (or once false, always false). If p(x) reads F T F T across the range, throwing away a half is no longer safe — the seam you deleted might have held the answer.
cships everything in Ddays” — more capacity is never worse, so feasibility only ever turns on. Bisect away.x?” across a random array — true in scattered spots, not a clean F…T line. (Peak-finding works only because of a different monotone argument about slopes, not because the array is sorted.)x works, does every larger x work too?” If you can't say yes, you don't have a binary-search problem yet — go find the real monotone quantity.Binary search works whenever the search space can be ordered and each midpoint comparison permanently eliminates one half. The classic case is a sorted array: if arr[mid] < target you discard everything to the left, cutting work in half with every step.
The loop invariant is the core idea: at every iteration, the answer (if it exists) lies within [lo, hi]. Every update must preserve that invariant. The loop terminates when the window shrinks to zero or one element.
hi = mid (not mid - 1) in lower-bound variants when mid itself might be the answer.Most interview binary-search problems don't hand you a sorted array — they give you a condition feasible(x) that is monotone: false for all small values of x and truefor all large ones (or vice versa). You never see the “sorted array” — you construct the sorted space from the problem constraints.
k?” — false for tiny k, true for large. Binary-search k.cenough?” — same shape.Once you see the predicate, the algorithm is mechanical: search the answer range [lo, hi] for the first true.
Unify all variants under one mental model: you are always looking for the first position where a predicate becomes true. For exact search the predicate is arr[i] >= target; for a feasibility search it's feasible(i). The lower-bound template (while lo < hi, hi = mid on true) handles every case cleanly.
When the feasibility check is itself O(n) (e.g. simulate a greedy), the overall cost is O(n log(hi−lo)) — still dramatically better than a brute-force scan of every candidate.
11 in a sorted array. Window [lo, hi] covers everything. Kill half every guess.Reach for binary search whenever the problem has a sorted structure or a monotone condition you can evaluate at any candidate value — especially when an O(log n) or O(n log n) bound is expected.
| "sorted array" + find / insert position / count | classic exact-match or lower-bound search |
| "find the minimum/maximum value such that f(x) is feasible" | binary search on the answer with a feasibility function |
| "minimize the maximum" or "maximize the minimum" | binary search on the answer — the optimal value has a monotone feasibility boundary |
| "rotated sorted array" — search or find minimum | determine which half is cleanly sorted, then narrow |
| O(log n) required and input has some ordering or monotone property | binary search on index or on the value/answer range |
| "Koko / ship packages / split array" — can we do it within a limit? | binary search on the answer; write a greedy feasible() check |
| "find the first / last occurrence" or "insert position" in sorted data | lower-bound template (while lo < hi, hi = mid) |
O(log n), but collecting every matching element is still O(k). If k can be large, consider a different structure.n ≤ 20). A linear scan is simpler and the constant factor of binary search adds cognitive overhead for no meaningful gain.f(x) is true-false-true across the range, there is no single boundary to find — binary search will silently return the wrong answer.When → The array is sorted and you want the index of an exact value (or -1 if absent). Use lo ≤ hi so the single-element window is still checked.
function binarySearch(arr: number[], target: number): number {
let lo = 0, hi = arr.length - 1;
while (lo <= hi) { // search space: [lo, hi] (inclusive)
const mid = lo + ((hi - lo) >> 1); // avoids integer overflow
if (arr[mid] === target) return mid; // found
if (arr[mid] < target) lo = mid + 1; // target is to the right
else hi = mid - 1; // target is to the left
}
return -1; // not found
}lo ≤ hi → the search space is the closed interval [lo, hi]. When lo passes hi the interval is empty and the target does not exist.When → You want the first index (or first value) where a monotone predicate becomes true: first element ≥ target, first feasible answer, insert position, etc. Use while lo < hi with hi = mid to keep the answer candidate in range.
// "First index where predicate(arr[i]) is true."
// Predicate must be monotone: false…false…TRUE…TRUE (no re-toggling).
function lowerBound(arr: number[], target: number): number {
let lo = 0, hi = arr.length; // hi = arr.length (one past end)
while (lo < hi) { // invariant: answer ∈ [lo, hi]
const mid = lo + ((hi - lo) >> 1);
if (arr[mid] < target) lo = mid + 1; // mid is definitely NOT the answer
else hi = mid; // mid might be the answer, keep it
}
return lo; // lo === hi, the first true position
}hi = arr.length (not length - 1) → if every element is smaller than target, the answer is “one past the end” (insert at the tail). Setting hi = arr.length lets the algorithm express that naturally without a special-case guard.When → The problem asks for the minimum (or maximum) value satisfying a condition — not an index in an array. Define a feasible(mid) check and binary-search the value range [lo, hi] directly.
// Binary-search on the ANSWER (a value range, not an index).
// Use when: "find min/max X such that feasible(X) is true/false."
function minFeasible(lo: number, hi: number): number {
// lo = smallest candidate answer, hi = largest candidate answer
while (lo < hi) {
const mid = lo + ((hi - lo) >> 1);
if (feasible(mid)) hi = mid; // mid works → try smaller
else lo = mid + 1; // mid too small → must go larger
}
return lo; // smallest value where feasible is true
}
// feasible() runs in O(n) → overall O(n log(hi - lo))
function feasible(mid: number): boolean {
// problem-specific check: e.g., "can we do the task in mid days?"
return true; // replace with real logic
}lo is the smallest possible answer (often 1 or max(arr)), hi is the largest (often sum(arr) or a problem constraint). Tighten them to reduce iterations.When → The array was sorted then rotated at an unknown pivot. One of the two halves around mid is always cleanly sorted — use that to decide which side contains the target.
// Search in a rotated sorted array (no duplicates).
function searchRotated(arr: number[], target: number): number {
let lo = 0, hi = arr.length - 1;
while (lo <= hi) {
const mid = lo + ((hi - lo) >> 1);
if (arr[mid] === target) return mid;
// Figure out which half is cleanly sorted.
if (arr[lo] <= arr[mid]) { // left half is sorted
if (arr[lo] <= target && target < arr[mid]) hi = mid - 1; // target in left
else lo = mid + 1; // target in right
} else { // right half is sorted
if (arr[mid] < target && target <= arr[hi]) lo = mid + 1; // target in right
else hi = mid - 1; // target in left
}
}
return -1;
}arr[lo] to arr[mid] (not to target) to determine which half is sorted. Then check whether target falls inside the sorted half; if yes, discard the other side.The most common bug: using lo = mid instead of lo = mid + 1 in the branch where mid is definitely not the answer. When lo === hi - 1, mid === lo, and if you set lo = mid again, nothing changes — infinite loop.
Rule: if the current mid is ruled out, always move the boundary past it (mid + 1 or mid - 1). Only use hi = mid when mid itself might still be the answer.
Use while (lo <= hi) for exact-match (closed interval — shrinks to empty when lo > hi) and while (lo < hi) for lower-bound / first-true (half-open — converges to a single candidate). Mixing them either skips the last candidate or loops forever at a two-element window.
Writing mid = (lo + hi) / 2 overflows in languages with fixed-width integers when lo + hi > MAX_INT. The safe form is lo + ((hi - lo) >> 1) (or lo + Math.floor((hi - lo) / 2) in TypeScript/JavaScript where numbers are 64-bit floats — overflow is rare but the idiom signals intent and is worth habituating).
In classic array search, lo and hi are indices. In binary-search-on-answer problems they are values (e.g., eating speeds, capacities). If you mix the two framings — say, initialising hi = arr.length - 1 when it should be sum(arr)— the search range is wrong and the algorithm silently produces a bad answer. Always ask: “what unit are my bounds in?”