Why it works
If a range is sorted (or a yes/no answer is monotonic), testing the middle tells you which half can be discarded. The skill in interviews isn’t the while-loop — it’s stating an invariant so you don’t off-by-one yourself.
Analogy: dictionary flip
Binary search is how you find a word in a paper dictionary: open the middle, decide left or right half, repeat. The skill isn’t the loop — it’s the sentence “everything left of lo is too small; everything at/right of hi is big enough.”
Template + tiny trace
def lower_bound(a, x):
# first index i with a[i] >= x
lo, hi = 0, len(a)
while lo < hi:
mid = (lo + hi) // 2
if a[mid] < x:
lo = mid + 1 # mid is too small
else:
hi = mid # mid might be answer
return lo
# a = [1,3,3,7], x = 3 → answers index 1
# start lo=0 hi=4 mid=2 (3) → hi=2
# mid=1 (3) → hi=1
# lo==hi==1 stopint lowerBound(int[] a, int x) {
// first index i with a[i] >= x
int lo = 0, hi = a.length;
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (a[mid] < x) {
lo = mid + 1; // mid is too small
} else {
hi = mid; // mid might be answer
}
}
return lo;
}
// a = [1,3,3,7], x = 3 → answers index 1
// start lo=0 hi=4 mid=2 (3) → hi=2
// mid=1 (3) → hi=1
// lo==hi==1 stopDry-run one example on the board before coding. Candidates who skip this often flip lo/hi updates under pressure.
Search on answer — full example
Problem shape: minimize capacity C to ship all packages in D days. Feasibility is monotonic: if C works, C+1 works. So binary search C.
def min_capacity(weights, days):
def ok(cap):
need = 1
cur = 0
for w in weights:
if cur + w > cap:
need += 1
cur = 0
cur += w
return need <= days
lo, hi = max(weights), sum(weights)
while lo < hi:
mid = (lo + hi) // 2
if ok(mid):
hi = mid
else:
lo = mid + 1
return lo
# weights=[1,2,3,4,5,6,7,8,9,10], days=5
# lo starts 10, hi 55 — search mid capacities until minimal okint minCapacity(int[] weights, int days) {
int lo = 0, hi = 0;
for (int w : weights) { lo = Math.max(lo, w); hi += w; }
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (ok(weights, days, mid)) hi = mid;
else lo = mid + 1;
}
return lo;
}
boolean ok(int[] weights, int days, int cap) {
int need = 1, cur = 0;
for (int w : weights) {
if (cur + w > cap) { need++; cur = 0; }
cur += w;
}
return need <= days;
}
// weights=[1,2,3,4,5,6,7,8,9,10], days=5
// lo starts 10, hi 55 — search mid capacities until minimal okWhat a good explanation sounds like
You: ‘The answer capacity is monotonic — if 30 works, 31 works — so I’ll binary search capacity between max(weight) and sum(weights). At mid I’ll simulate days needed; if too many days, mid is too small and I raise lo.’
That paragraph is the interview. The code is just the receipt.
When to reach for this pattern
Two flavors only: (1) find a position in a sorted sequence, (2) binary search the answer value because feasibility is monotonic. Interviews punish fuzzy lo/hi updates — pick one invariant and stick to it.
Core template + worked trace
Lower bound — first index with a[i] >= x. Half-open [lo, hi).
def lower_bound(a: list[int], x: int) -> int:
# Invariant: all indices < lo are < x; all indices >= hi are >= x (or past end)
lo, hi = 0, len(a)
while lo < hi:
mid = (lo + hi) // 2
if a[mid] < x:
lo = mid + 1 # mid too small
else:
hi = mid # mid might be first good
return lo
# a=[1,3,3,7], x=3
# lo,hi=0,4 mid=2 (3) → hi=2
# mid=1 (3) → hi=1
# lo==hi==1 → first 3int lowerBound(int[] a, int x) {
// Invariant: all indices < lo are < x; all indices >= hi are >= x (or past end)
int lo = 0, hi = a.length;
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (a[mid] < x) {
lo = mid + 1; // mid too small
} else {
hi = mid; // mid might be first good
}
}
return lo;
}
// a=[1,3,3,7], x=3
// lo,hi=0,4 mid=2 (3) → hi=2
// mid=1 (3) → hi=1
// lo==hi==1 → first 3Search-on-answer skeleton (shipping capacity style):
def min_feasible(lo: int, hi: int, ok) -> int:
# ok(mid) True ⇒ mid works; assume monotonic: ok(m) ⇒ ok(m+1)
while lo < hi:
mid = (lo + hi) // 2
if ok(mid):
hi = mid
else:
lo = mid + 1
return loint minFeasible(int lo, int hi, java.util.function.IntPredicate ok) {
// ok(mid) true ⇒ mid works; assume monotonic: ok(m) ⇒ ok(m+1)
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (ok.test(mid)) hi = mid;
else lo = mid + 1;
}
return lo;
}Edge cases & common bugs
Complexity — say it aloud
Interview talk track
You: ‘I’ll maintain the invariant that everything left of lo is too small and everything at or right of hi is big enough. I shrink until lo == hi — the first feasible answer. For capacity, I’ll prove monotonicity: if C works, C+1 works.’
Practice set
- Binary Search / Lower Bound
- Search Insert Position
- Find First and Last Position in Sorted Array
- Search in Rotated Sorted Array
- Koko Eating Bananas
- Capacity To Ship Packages Within D Days
- Split Array Largest Sum
- Median of Two Sorted Arrays (stretch)
Harder follow-up
Harder variant: Split Array Largest Sum — minimize the largest subarray sum when splitting into m parts. Same search-on-answer; ok(cap) counts how many parts you need greedily.
Pattern bank: more questions + efficient solutions
Five search staples. Always name the predicate: ‘first true’, ‘last false’, or ‘minimum feasible capacity’.
Q: Search in Rotated Sorted Array — nums was sorted ascending then rotated; find target’s index or −1. Assume unique elements.
def search_rotated(nums, target):
lo, hi = 0, len(nums) - 1
while lo <= hi:
mid = (lo + hi) // 2
if nums[mid] == target:
return mid
if nums[lo] <= nums[mid]: # left half sorted
if nums[lo] <= target < nums[mid]:
hi = mid - 1
else:
lo = mid + 1
else: # right half sorted
if nums[mid] < target <= nums[hi]:
lo = mid + 1
else:
hi = mid - 1
return -1
# O(log n) time, O(1) spaceint searchRotated(int[] nums, int target) {
int lo = 0, hi = nums.length - 1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
if (nums[mid] == target) return mid;
if (nums[lo] <= nums[mid]) { // left sorted
if (nums[lo] <= target && target < nums[mid]) hi = mid - 1;
else lo = mid + 1;
} else { // right sorted
if (nums[mid] < target && target <= nums[hi]) lo = mid + 1;
else hi = mid - 1;
}
}
return -1;
}
// O(log n) time, O(1) spaceQ: Find First and Last Position of Element in Sorted Array — return [first, last] indices of target, or [−1, −1] if absent.
def search_range(nums, target):
def lower(x):
lo, hi = 0, len(nums)
while lo < hi:
mid = (lo + hi) // 2
if nums[mid] < x:
lo = mid + 1
else:
hi = mid
return lo
L = lower(target)
if L == len(nums) or nums[L] != target:
return [-1, -1]
R = lower(target + 1) - 1
return [L, R]
# O(log n) time, O(1) spaceint[] searchRange(int[] nums, int target) {
int L = lowerBound(nums, target);
if (L == nums.length || nums[L] != target) return new int[]{-1, -1};
int R = lowerBound(nums, target + 1) - 1;
return new int[]{L, R};
}
int lowerBound(int[] a, int x) {
int lo = 0, hi = a.length;
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (a[mid] < x) lo = mid + 1;
else hi = mid;
}
return lo;
}
// O(log n) time, O(1) spaceQ: Koko Eating Bananas — piles of bananas, h hours; find minimum integer speed k such that Koko finishes all piles in ≤ h hours (ceil division per pile).
import math
def min_eating_speed(piles, h):
lo, hi = 1, max(piles)
while lo < hi:
mid = (lo + hi) // 2
hours = sum(math.ceil(p / mid) for p in piles)
if hours <= h:
hi = mid
else:
lo = mid + 1
return lo
# O(n log M) time, O(1) spaceint minEatingSpeed(int[] piles, int h) {
int lo = 1, hi = 0;
for (int p : piles) hi = Math.max(hi, p);
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
long hours = 0;
for (int p : piles) hours += (p + mid - 1L) / mid;
if (hours <= h) hi = mid;
else lo = mid + 1;
}
return lo;
}
// O(n log M) time, O(1) spaceQ: Median of Two Sorted Arrays — find median of two sorted arrays in O(log(min(m, n))) by partitioning (hard; sketch is interview-OK).
def find_median_sorted_arrays(a, b):
if len(a) > len(b):
a, b = b, a
m, n = len(a), len(b)
lo, hi = 0, m
half = (m + n + 1) // 2
while lo <= hi:
i = (lo + hi) // 2 # cut in a
j = half - i # cut in b
a_left = a[i - 1] if i else float("-inf")
a_right = a[i] if i < m else float("inf")
b_left = b[j - 1] if j else float("-inf")
b_right = b[j] if j < n else float("inf")
if a_left <= b_right and b_left <= a_right:
if (m + n) % 2:
return float(max(a_left, b_left))
return (max(a_left, b_left) + min(a_right, b_right)) / 2.0
if a_left > b_right:
hi = i - 1
else:
lo = i + 1
raise ValueError("unreachable")
# O(log(min(m,n))) time, O(1) spacedouble findMedianSortedArrays(int[] a, int[] b) {
if (a.length > b.length) return findMedianSortedArrays(b, a);
int m = a.length, n = b.length;
int lo = 0, hi = m, half = (m + n + 1) / 2;
while (lo <= hi) {
int i = (lo + hi) / 2, j = half - i;
int aLeft = i == 0 ? Integer.MIN_VALUE : a[i - 1];
int aRight = i == m ? Integer.MAX_VALUE : a[i];
int bLeft = j == 0 ? Integer.MIN_VALUE : b[j - 1];
int bRight = j == n ? Integer.MAX_VALUE : b[j];
if (aLeft <= bRight && bLeft <= aRight) {
if (((m + n) & 1) == 1) return Math.max(aLeft, bLeft);
return (Math.max(aLeft, bLeft) + Math.min(aRight, bRight)) / 2.0;
}
if (aLeft > bRight) hi = i - 1;
else lo = i + 1;
}
throw new IllegalStateException();
}
// O(log(min(m,n))) time, O(1) spaceQ: Split Array Largest Sum — split nums into m non-empty contiguous subarrays; minimize the largest subarray sum.
def split_array(nums, m):
def ok(cap):
pieces = 1
cur = 0
for x in nums:
if cur + x > cap:
pieces += 1
cur = x
if pieces > m:
return False
else:
cur += x
return True
lo, hi = max(nums), sum(nums)
while lo < hi:
mid = (lo + hi) // 2
if ok(mid):
hi = mid
else:
lo = mid + 1
return lo
# O(n log S) time, O(1) spaceint splitArray(int[] nums, int m) {
int lo = 0, hi = 0;
for (int x : nums) { lo = Math.max(lo, x); hi += x; }
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (canSplit(nums, m, mid)) hi = mid;
else lo = mid + 1;
}
return lo;
}
boolean canSplit(int[] nums, int m, int cap) {
int pieces = 1, cur = 0;
for (int x : nums) {
if (cur + x > cap) { pieces++; cur = x; if (pieces > m) return false; }
else cur += x;
}
return true;
}
// O(n log S) time, O(1) space