Lesson 6 of 8 · 48 min

Modified binary search

Boundary-safe binary search, rotated arrays, first/last occurrence, and search-on-answer (Koko, ship packages) with capacity-planning metaphors.

Binary search is not only “find in sorted array”

The career-changing upgrade is search-on-answer: when feasibility is monotonic in some integer capacity/time/threshold X, binary search X and run a linear checker. Koko Eating Bananas, Capacity to Ship Packages, Split Array Largest Sum — same skeleton. Production metaphor: “is N workers enough to finish by deadline?” Classic rotated-array and first/last occurrence still appear; they train boundary discipline (lo/hi/mid bias).

Core loop hygiene: decide inclusive bounds [lo, hi]; compute mid = lo + (hi−lo)//2; define whether answer is on left or right; avoid infinite loops by ensuring lo/hi move. For lower_bound (first True): if pred(mid): hi=mid; else lo=mid+1. Upper bound variants flip. State the predicate in words before code.

Rotated sorted array: one side of mid is always sorted. If target in sorted side’s range, search there; else the other. First/last position of target: two binary searches with different move rules. Complexity O(log n) — if you scan linearly after finding one hit, say why or fix to full binary.

Classic BS and first/last

python

1LOWER BOUND — first index with a[i] >= target (sorted a)23def lower_bound(a: list[int], target: int) -> int:4    lo, hi = 0, len(a)  # hi exclusive5    while lo < hi:6        mid = (lo + hi) // 27        if a[mid] >= target:8            hi = mid9        else:10            lo = mid + 111    return lo  # in [0, n]; n means all < target1213# First/last occurrence: lower_bound(t) and lower_bound(t+1)-1 with existence checks.

Rotated sorted array

python

1SEARCH IN ROTATED SORTED ARRAY — identify sorted half23def search_rotated(a: list[int], target: int) -> int:4    lo, hi = 0, len(a) - 15    while lo <= hi:6        mid = (lo + hi) // 27        if a[mid] == target:8            return mid9        if a[lo] <= a[mid]:  # left half sorted10            if a[lo] <= target < a[mid]:11                hi = mid - 112            else:13                lo = mid + 114        else:  # right half sorted15            if a[mid] < target <= a[hi]:16                lo = mid + 117            else:18                hi = mid - 119    return -1

Duplicates in rotated array break the clean “which half sorted” test — may need lo++ when a[lo]==a[mid]==a[hi]. Mention as follow-up; do not panic into O(n) without saying so.

Search-on-answer: Koko and ship packages

Koko: minimize eating speed k such that hours_needed(k) ≤ h. feasible(k) monotonically true as k grows. lo=1, hi=max(piles). Ship packages in D days: minimize capacity C; feasible(C) = can ship in ≤ D days with greedy packing. Same binary skeleton, different checker. Split array largest sum: minimize largest subarray sum with m splits — again search on answer.

python

1SEARCH ON ANSWER — capacity to ship packages within D days23def ship_within_days(weights: list[int], days: int) -> int:4    def feasible(cap: int) -> bool:5        need, cur = 1, 06        for w in weights:7            if w > cap:8                return False9            if cur + w > cap:10                need += 111                cur = 012            cur += w13        return need <= days1415    lo, hi = max(weights), sum(weights)16    while lo < hi:17        mid = (lo + hi) // 218        if feasible(mid):19            hi = mid20        else:21            lo = mid + 122    return lo2324# O(n log S) with S = sum(weights). Narrate lo/hi meaning: min possible cap vs max.

Production: capacity planning — binary search number of replicas until p99 latency SLO passes in a load test harness (feasible = load test). Same mental model as Koko, with a more expensive predicate. Interviewers love when you name that parallel briefly.

Koko as the canonical search-on-answer drill

Koko Eating Bananas: piles of bananas, speed k bananas/hour, whole hours via ceiling division, finish within h hours — minimize k. feasible(k) = sum(ceil(p/k) for p in piles) ≤ h. Bounds: lo=1, hi=max(piles). The ceiling trick: (p + k − 1)//k. Dry-run a 3-pile example with h tight enough that only one k works — proves your hi=mid branch.

python

1KOKO EATING BANANAS — search-on-answer twin of ship packages23def min_eating_speed(piles: list[int], h: int) -> int:4    def hours(k: int) -> int:5        return sum((p + k - 1) // k for p in piles)67    lo, hi = 1, max(piles)8    while lo < hi:9        mid = (lo + hi) // 210        if hours(mid) <= h:11            hi = mid12        else:13            lo = mid + 114    return lo1516# Same skeleton as ship_within_days — only feasible changes.17# That sentence is the transfer skill interviewers grade.

Split Array Largest Sum is the same family: minimize the largest bucket sum when splitting into m contiguous parts. feasible(limit) = can split with each part sum ≤ limit using ≤ m parts. Once you have shipped packages and Koko, this should feel like renaming variables — if it does not, re-drill the skeleton until it does.

Binary Search — NeetCodeNeetCode

Interview prep

Binary search rounds fail on boundary bugs more than on ideas. Practice writing lower_bound and one search-on-answer from a blank file under 12 minutes.

01“When search-on-answer?” → minimize/maximize X with monotonic feasible(X).
02“Koko template?” → lo=1 hi=max pile; feasible hours ≤ h; minimize lo.
03“Ship packages lo/hi?” → lo=max(weight) hi=sum; feasible days ≤ D.
04“Rotated array key?” → at mid, at least one half is sorted; discard half via range test.
05“First occurrence?” → lower_bound style; do not scan linearly after find.
06“Infinite loop causes?” → mid computed wrong; lo/hi not moving; use hi=mid vs mid-1 carefully.
07“Duplicates in rotated?” → when equals blur sorted half, may shrink lo/hi linearly worst case.
08“Complexity speech?” → O(log n) index BS; O(n log RANGE) search-on-answer.
09"Overflow-safe mid?" -> lo + (hi-lo)//2.
10"Answer-space examples?" -> Koko, ship packages, split array largest sum, min max distance.
11"Rotated half choice?" -> find sorted half; if target in range search there else other.
12"Lower bound?" -> first i with a[i] >= target; hi exclusive template.
13"When is BS wrong?" -> when the predicate is not monotonic.
14"Complexity with expensive P?" -> O(P_cost * log domain); state P_cost explicitly.

Write feasible(x) first as a pure function. If you cannot unit-test feasible on paper, the binary search shell will only hide the bug.

articleSorting & searching — Tech Interview HandbookTech Interview Handbook docsNeetCode — Koko Eating BananasNeetCode docsLeetCode — Capacity To Ship Packages Within D DaysLeetCode articleAlgoMaster patternsAlgoMaster

Templates: lower bound + answer-space (Koko)

Pick one bound style (lo < hi with hi exclusive, or lo <= hi) and never mix mid+/-1 soup mid-round. mid = lo + (hi-lo)//2 is overflow-safe taste even in Python. First/last occurrence: on match keep searching left or right. Rotated array: identify sorted half; test if target is in range. Answer-space BS: Koko, ship packages, split array largest sum — binary search the answer while is_feasible(mid) is monotonic. Production: git bisect, autoscaling capacity, min machines for latency SLO. Force: I search minimum X such that P(X) holds; P is monotonic. Write the invariant above the loop: answer is always in [lo, hi). isBadVersion is lower_bound on booleans. Koko rewrites as hours(k) <= h searching k in [1, max(piles)]. Ship packages uses can_ship(cap) — same skeleton. Rotated array needs the which-half-is-sorted branch; dry-run [4,5,6,7,0,1,2] target 0 and target 3 (missing). Infinite loops almost always come from lo=mid instead of lo=mid+1 when the predicate says go right. Build a personal template card: (1) lower_bound, (2) upper_bound, (3) answer-space min X with P(X). Re-type all three from memory until the mid update is automatic. Common live failure: using lo <= hi with hi = mid - 1 and lo = mid on a max-search, which infinite-loops when lo+1==hi. Draw the lo/hi/mid table for three iterations on paper during the interview — Verification loves that. For rotated arrays with duplicates, admit the worst case degrades to O(n) and say how you would fall back. That honesty scores higher than a wrong claim of pure O(log n).

python

1LOWER BOUND — first index with a[i] >= target23def lower_bound(a: list[int], target: int) -> int:4    lo, hi = 0, len(a)  # hi exclusive5    while lo < hi:6        mid = lo + (hi - lo) // 27        if a[mid] < target:8            lo = mid + 19        else:10            hi = mid11    return lo  # in [0..n]; n means all < target1213# Invariant: answer lives in [lo, hi). Prefer this over ad-hoc branches.14# upper_bound: first index with a[i] > target (change < to <=).

python

1KOKO EATING BANANAS — binary search on answer23def min_eating_speed(piles: list[int], h: int) -> int:4    def hours(k: int) -> int:5        return sum((p + k - 1) // k for p in piles)67    lo, hi = 1, max(piles)8    while lo < hi:9        mid = lo + (hi - lo) // 210        if hours(mid) <= h:11            hi = mid12        else:13            lo = mid + 114    return lo1516# hours(k) decreases as k grows — monotonicity licenses BS on speed.17# Complexity: O(n log M) where M = max(piles).

Graders + tiers. Invariant + inclusive/exclusive bounds. Classic vs answer-space. No infinite lo=mid loops. Verify n=1, all equal, missing target, rotated with duplicates (mention harder case). FAANG: rotated + Koko-style. India OA: classic + first/last. AI lab: expensive predicates (each probe costs) — discuss probe budget. If the interviewer changes the cost of is_feasible, your complexity sentence must include that factor. MIT OCW 6.006 lectures on binary search correctness are worth one evening if your invariants still feel magical rather than proved. Pair that with NeetCode binary search playlist and Labuladong's four-line framework. Your exit criterion: implement lower_bound, search-rotated, and Koko from a blank file in under 12 minutes each with a spoken invariant. If any of the three still needs a peek at a solution video, re-do that template the next morning before new problems. Answer-space BS is a force multiplier: once installed, half of "hard" BS prompts collapse to the same card.

Koko Eating Bananas — NeetCodeNeetCode articleSorting & Searching cheatsheet — TIHTech Interview Handbook articleBinary search framework — LabuladongLabuladong

Worked answer-space family. (1) Define the domain of the answer (speeds, capacities). (2) Write is_feasible(x) and prove monotonicity in one sentence. (3) Binary search the boundary. (4) Return lo (min true) or hi (max true) per the template. (5) Dry-run the smallest domain (single pile, h=1 edge). This family covers a surprising fraction of medium/hard BS interviews once you stop hunting for a sorted array that may not exist.

Checkpoint

“Minimum capacity to ship all packages within D days, packages must stay in order.” First words out of your mouth?

ADynamic programming over subsets of days — start coding DP tableBSearch-on-answer: binary search capacity in [max(weight), sum]; feasible packs greedily into ≤ D daysCTwo pointers on the weights array only

Checkpoint

feasible(cap) is true for all cap ≥ C*. Your binary search should return?

AAny true cap in the rangeBThe minimum cap where feasible becomes true (lower boundary)CThe maximum cap always sum(weights)

Checkpoint

Rotated array search: a[lo] <= a[mid], target < a[lo]. Where next?

ASearch left half only alwaysBSearch right half — target is outside the sorted left rangeCReturn -1 immediately

Checkpoint

Off-by-one: while lo < hi; if feasible(mid): hi=mid; else lo=mid. Bug?

ANo bug — always terminatesBelse must be lo=mid+1 so the search range shrinks when mid is infeasibleCMust use recursive binary search only

Checkpoint

Production: “smallest number of workers so nightly ETL finishes by 6am.” Interview framing?

ALinearly try 1..n workers only, never binary searchBBinary search worker count; feasible(w) = simulated schedule finishes by deadline (monotonic in w)CThis is only a system design question, not coding

Can you invent feasible(x) for a novel capacity prompt and code lower-bound binary search without infinite loops?

New to itGetting thereConfident

Takeaways

Binary search domains: indices OR answer values.
Search-on-answer when feasible is monotonic.
Rotated arrays: discard using the sorted half’s range.
lo/hi movement rules prevent infinite loops.
Production parallel: capacity planning / SLO search.

Next: trees and graphs — BFS/DFS choice, topo sort, clone, word ladder.

Sources

Free to read · better with Enzo

Learn it with Enzo

Save your progress, answer the checkpoints, and let Enzo quiz you on what you just read.

Continue with Enzo Sign up free