ChannelPulse
Binary search, and why your version has a bug
Binary search is famously easy to get subtly wrong. The cure is a loop invariant instead of a remembered template — and once you have the invariant, "binary search on the answer" stops being a separate trick and becomes the same algorithm on a different array.
What you'll be able to do
- State the loop invariant for a half-open binary search and use it to derive every boundary decision
- Write lower-bound and upper-bound searches that are correct on duplicates and on empty input
- Prove that the loop terminates, and identify the two edits that make it hang
- Apply binary search to a monotone predicate over an answer space rather than an array
Before this: complexity-honestly
Binary search has a reputation, and the reputation is earned: the standard bug — a midpoint computed as (lo + hi) / 2 overflowing on large indices — sat undetected in widely used library and textbook implementations for years before it was publicly written up. If it can hide there, it can hide in your interview answer.
The fix is not to memorise a better template. It is to carry an invariant, because an invariant tells you what every boundary decision should be instead of asking you to recall it.
Each probe discards half of what remains. Eight elements, three probes. The animation shows the surviving RANGE rather than just the midpoint, because the range is what the invariant is about.
Not a binary search video — a university lecture on how you *prove* that a simple rule is correct. It is here because that is the habit this lesson depends on: the reason a binary search terminates and returns the right index is an invariant you can state, not a template you memorised. Watch the first ten minutes if you are short on time. No chapter markers.
The invariant
Use a half-open interval: lo is inclusive, hi is exclusive, so the live range is [lo, hi) and it is empty exactly when lo === hi. Every decision below falls out of this one choice.
Half-open is worth adopting as a habit rather than a preference. hi = length needs no - 1. The range size is exactly hi - lo. Empty is lo === hi, not lo > hi. And the loop condition is lo < hi, which is the same condition as "the range is non-empty". Every off-by-one you would otherwise have to remember becomes a consequence.
1The plain search, derived rather than recalled▾
// Returns an index of `target`, or -1.
function search(nums, target) {
let lo = 0;
let hi = nums.length; // exclusive: [lo, hi) is the live range
while (lo < hi) { // non-empty range
// No overflow: lo + (hi-lo)/2 never exceeds hi, whereas (lo+hi) can exceed
// the integer range in a fixed-width language. JS numbers make this
// theoretical here, but the habit is what interviewers look for.
const mid = lo + ((hi - lo) >> 1);
if (nums[mid] === target) return mid;
if (nums[mid] < target) lo = mid + 1; // target is strictly right of mid
else hi = mid; // target is strictly left of mid
}
return -1; // range is empty: not present
}
console.log(search([1, 3, 5, 7, 9, 11, 13, 15], 13)); // 6
console.log(search([1, 3, 5, 7, 9, 11, 13, 15], 4)); // -1
console.log(search([], 1)); // -1 -> loop never runs
console.log(search([5], 5)); // 0# Returns an index of `target`, or -1.
def search(nums, target):
lo = 0
hi = len(nums) # exclusive: [lo, hi) is the live range
while lo < hi: # non-empty range
# Python integers are arbitrary precision, so `(lo + hi) // 2` cannot
# overflow here. Write it this way anyway: it is the form that stays
# correct when you write the same loop in a fixed-width language, and
# it is the form interviewers are listening for.
mid = lo + (hi - lo) // 2
if nums[mid] == target:
return mid
if nums[mid] < target:
lo = mid + 1 # target is strictly right of mid
else:
hi = mid # target is strictly left of mid
return -1 # range is empty: not present
print(search([1, 3, 5, 7, 9, 11, 13, 15], 13)) # 6
print(search([1, 3, 5, 7, 9, 11, 13, 15], 4)) # -1
print(search([], 1)) # -1 -> loop never runs
print(search([5], 5)) # 06 -1 -1 0
Trace the invariant through each branch. If nums[mid] < target, the target cannot be at mid or anywhere left of it, so the live range becomes [mid+1, hi) — still contains the answer, and strictly smaller. If nums[mid] > target, the target is not at mid or right of it, so the range becomes [lo, mid) — again smaller, because mid < hi. Both branches satisfy (a) and (b). Done; the loop is correct.
2Prove it terminates, and find the two edits that break it▾
Termination needs hi - lo to strictly decrease. In the left branch, lo becomes mid + 1, which is strictly greater than lo because mid >= lo. In the right branch, hi becomes mid, which is strictly less than hi because mid < hi — and mid < hi holds precisely because mid is the floor of the midpoint of a non-empty range.
Two innocuous-looking edits destroy this, and both are common in real interviews:
Writing lo = mid instead of lo = mid + 1. On a two-element range where mid === lo, the range stops shrinking and the loop spins forever. This is the classic hang.
Rounding the midpoint up (mid = lo + Math.ceil((hi - lo) / 2)) while still assigning hi = mid. Now mid can equal hi when the range has one element, and again nothing shrinks.
Duplicates, and why "find the target" is the wrong goal
The version above returns some index of the target. With duplicates that is rarely what a problem wants. The two useful primitives are boundaries, not hits:
- lower bound: the first index where
nums[i] >= target - upper bound: the first index where
nums[i] > target
Both always exist as a position in [0, n] — returning n means "everything is smaller". From those two, everything else is arithmetic: presence is lower < n && nums[lower] === target, the count of occurrences is upper - lower, and the insertion position is lower itself.
3Boundary searches with no equality test at all▾
// First index with nums[i] >= target. Result is in [0, n].
function lowerBound(nums, target) {
let lo = 0;
let hi = nums.length;
while (lo < hi) {
const mid = lo + ((hi - lo) >> 1);
if (nums[mid] < target) lo = mid + 1; // mid is too small: answer is right of it
else hi = mid; // mid qualifies: answer is at mid or left
}
return lo;
}
// First index with nums[i] > target. One character different: <= instead of <.
function upperBound(nums, target) {
let lo = 0;
let hi = nums.length;
while (lo < hi) {
const mid = lo + ((hi - lo) >> 1);
if (nums[mid] <= target) lo = mid + 1;
else hi = mid;
}
return lo;
}
const nums = [1, 2, 2, 2, 3, 5, 5, 9];
for (const t of [2, 5, 4, 0, 10]) {
const lo = lowerBound(nums, t);
const hi = upperBound(nums, t);
console.log(`target ${String(t).padStart(2)}: lower=${lo} upper=${hi} count=${hi - lo} present=${lo < nums.length && nums[lo] === t}`);
}# First index with nums[i] >= target. Result is in [0, n].
# This is `bisect.bisect_left` from the standard library -- write it out once,
# then use `bisect` in real code and say so in an interview.
def lower_bound(nums, target):
lo = 0
hi = len(nums)
while lo < hi:
mid = lo + (hi - lo) // 2
if nums[mid] < target:
lo = mid + 1 # mid is too small: answer is right of it
else:
hi = mid # mid qualifies: answer is at mid or left
return lo
# First index with nums[i] > target -- `bisect.bisect_right`. One character
# different from the loop above: <= instead of <.
def upper_bound(nums, target):
lo = 0
hi = len(nums)
while lo < hi:
mid = lo + (hi - lo) // 2
if nums[mid] <= target:
lo = mid + 1
else:
hi = mid
return lo
nums = [1, 2, 2, 2, 3, 5, 5, 9]
for t in [2, 5, 4, 0, 10]:
lo = lower_bound(nums, t)
hi = upper_bound(nums, t)
present = lo < len(nums) and nums[lo] == t
print(f"target {str(t).rjust(2)}: lower={lo} upper={hi} count={hi - lo} present={present}")target 2: lower=1 upper=4 count=3 present=True target 5: lower=5 upper=7 count=2 present=True target 4: lower=5 upper=5 count=0 present=False target 0: lower=0 upper=0 count=0 present=False target 10: lower=8 upper=8 count=0 present=False
There is no === target branch in either function, and that is the point: removing the early return is what makes the result well defined on duplicates. The two functions differ by exactly one character — < versus <= — which is a nice thing to be able to point out, because it shows the shared structure is real and not a coincidence.
Binary search on the answer
Here is the reframing that makes binary search a general tool rather than an array operation.
Strip the array out of the invariant. What the algorithm really needs is a monotone predicate: a boolean function ok(x) that is false for every x below some threshold and true for every x at or above it. Sorted-array search is just the special case where ok(i) = nums[i] >= target.
ok: false false false TRUE TRUE TRUE
^
lower bound = the answerIf you can write ok(x) for a candidate answer, you can binary search the answer space — even if it is a range of speeds, capacities, or times, and even if there is no array anywhere.
4Recognise the prompt▾
The tell is a superlative plus a feasibility check: "minimum capacity such that…", "smallest number of days to…", "maximum size such that…". Then ask one question: if a candidate answer works, does every larger one also work? If yes, the predicate is monotone and you are done thinking.
5Write the predicate first, then the search▾
The predicate is where the real work is; the search around it is the nine lines you already have.
// Ship packages in order within `days`. What is the smallest ship capacity?
// Monotone: if capacity C works, any capacity > C also works -- you can always
// carry more. So `ok` is false, false, ..., true, true and we want the boundary.
function shipWithinDays(weights, days) {
const ok = (capacity) => {
let daysUsed = 1;
let load = 0;
for (const w of weights) {
if (w > capacity) return false; // this package can never be carried
if (load + w > capacity) { // start a new day
daysUsed++;
load = 0;
}
load += w;
}
return daysUsed <= days;
};
// Bounds: the largest single package is the smallest conceivable capacity,
// and the total is always enough (one day). Both are provable, not guessed.
let lo = Math.max(...weights);
let hi = weights.reduce((a, b) => a + b, 0);
// Same half-open lower-bound search, over capacities instead of indices.
while (lo < hi) {
const mid = lo + Math.floor((hi - lo) / 2);
if (ok(mid)) hi = mid; // mid works: the answer is mid or smaller
else lo = mid + 1; // mid fails: the answer is strictly larger
}
return lo;
}
console.log(shipWithinDays([1, 2, 3, 4, 5, 6, 7, 8, 9, 10], 5)); // 15
console.log(shipWithinDays([3, 2, 2, 4, 1, 4], 3)); // 6
console.log(shipWithinDays([1, 2, 3, 1, 1], 4)); // 3# Ship packages in order within `days`. What is the smallest ship capacity?
# Monotone: if capacity C works, any capacity > C also works -- you can always
# carry more. So `ok` is False, False, ..., True, True and we want the boundary.
def ship_within_days(weights, days):
def ok(capacity):
days_used = 1
load = 0
for w in weights:
if w > capacity:
return False # this package can never be carried
if load + w > capacity: # start a new day
days_used += 1
load = 0
load += w
return days_used <= days
# Bounds: the largest single package is the smallest conceivable capacity,
# and the total is always enough (one day). Both are provable, not guessed.
lo = max(weights)
hi = sum(weights)
# Same half-open lower-bound search, over capacities instead of indices.
while lo < hi:
mid = lo + (hi - lo) // 2
if ok(mid):
hi = mid # mid works: the answer is mid or smaller
else:
lo = mid + 1 # mid fails: the answer is strictly larger
return lo
print(ship_within_days([1, 2, 3, 4, 5, 6, 7, 8, 9, 10], 5)) # 15
print(ship_within_days([3, 2, 2, 4, 1, 4], 3)) # 6
print(ship_within_days([1, 2, 3, 1, 1], 4)) # 315 6 3
Complexity: O(n log S) where S is the width of the answer range — each predicate evaluation is a linear scan, and there are log S of them. State it that way. Candidates often say "O(log n)" out of habit and it is wrong; the predicate cost is the dominant term.
The family, and one honest limit
| Prompt | Predicate | Search space |
|---|---|---|
| First/last position of a target | nums[i] >= target | Indices |
| Insertion position | nums[i] >= target | Indices, [0, n] |
| Square root, floor | x * x > n | [0, n+1) |
| Minimum ship capacity, minimum eating speed | Greedy feasibility scan | Capacities |
| Split array into k parts, minimise the largest sum | Greedy count-of-parts | Sums |
| Kth smallest in a sorted matrix | Count of entries <= x | Values, not positions |
| Rotated sorted array | Compare nums[mid] to an endpoint to find the sorted half | Indices |
The last row is the one that resists the invariant framing, and it is worth being honest about in an interview rather than pretending otherwise. A rotated array is not monotone, so there is no single predicate. The trick is that one of the two halves around mid is always properly sorted; you test which, then decide whether the target lies in that sorted half. It is still "discard half per step", but the discard rule needs a case analysis, and with duplicates the worst case degrades to O(n) — you cannot always tell which half is sorted when nums[lo] === nums[mid] === nums[hi]. Saying that out loud is worth more than a slick answer that quietly assumes distinct values.