Basics
The idea behind the pattern, why it is correct, and the clues in a question that point to it.
1.1Core idea
What the pattern does, in plain words.
Keep a range where the answer must lie. Test the middle and discard the half that cannot contain it. 'Binary search on the answer' applies the same idea to a range of possible answers with a feasibility check.
Binary search works whenever a yes/no question flips exactly once across a sorted range: false, false, …, true, true. Checking the middle tells you which half holds the first true, so every step halves the range and about log₂ n steps are enough. 'Binary search on the answer' applies the same idea to a range of possible answers instead of an array.
Typical cost: O(log n) per search; O(n log range) for search on the answer
1.2Recognition signals
If a question has one of these clues, try this pattern first.
Question
A classic interview problem from this family. Read it carefully and plan the approach before writing any code.
2.1Koko Eating Bananas
The problem statement, then the plan you would say out loud.
Piles of bananas, h hours. Find the minimum eating speed k to finish in time.
Plan before you code
- Speed range is 1 to max(pile).
- Feasible(k): total hours = sum(ceil(p / k)) ≤ h. It is monotonic in k.
- Binary search for the first feasible speed.
Detailed answer
First the reusable template, then the worked solution built from it and a walk through it one step at a time.
3.1Template
Memorise this shape. Most problems in this family are this code plus one twist.
First value where check() becomes true
1// smallest x in [lo, hi] with check(x) === true2function firstTrue(lo: number, hi: number, check: (x: number) => boolean): number {3 while (lo < hi) {4 const mid = lo + Math.floor((hi - lo) / 2);5 if (check(mid)) hi = mid; // mid might be the answer6 else lo = mid + 1; // answer is right of mid7 }8 return lo;9}1// smallest x in [lo, hi] with check(x) == true2fun firstTrue(low: Int, high: Int, check: (Int) -> Boolean): Int {3 var lo = low4 var hi = high5 while (lo < hi) {6 val mid = lo + (hi - lo) / 27 if (check(mid)) hi = mid // mid might be the answer8 else lo = mid + 1 // answer is right of mid9 }10 return lo11}1// smallest x in [lo, hi] with check.test(x) == true2static int firstTrue(int lo, int hi, IntPredicate check) {3 while (lo < hi) {4 int mid = lo + (hi - lo) / 2;5 if (check.test(mid)) hi = mid; // mid might be the answer6 else lo = mid + 1; // answer is right of mid7 }8 return lo;9}- Loop until the range is a single value.
- If mid works, keep it and search left.
- Otherwise the answer is strictly to the right.
3.2Solution
Strict TypeScript, type-checked and tested.
Koko Eating Bananas
1function minEatingSpeed(piles: number[], h: number): number {2 const can = (k: number) =>3 piles.reduce((hours, p) => hours + Math.ceil(p / k), 0) <= h;4 let lo = 1, hi = Math.max(...piles);5 while (lo < hi) {6 const mid = Math.floor((lo + hi) / 2);7 if (can(mid)) hi = mid;8 else lo = mid + 1;9 }10 return lo;11}1fun minEatingSpeed(piles: IntArray, h: Int): Int {2 fun hours(k: Int): Long = piles.sumOf { ((it + k - 1) / k).toLong() } // ceil(p / k)3 var lo = 14 var hi = piles.max()5 while (lo < hi) {6 val mid = (lo + hi) / 27 if (hours(mid) <= h) hi = mid8 else lo = mid + 19 }10 return lo11}1static int minEatingSpeed(int[] piles, int h) {2 int lo = 1, hi = Arrays.stream(piles).max().getAsInt();3 while (lo < hi) {4 int mid = (lo + hi) / 2;5 if (hoursAt(piles, mid) <= h) hi = mid;6 else lo = mid + 1;7 }8 return lo;9}10 11static long hoursAt(int[] piles, int k) {12 long hours = 0;13 for (int p : piles) hours += (p + k - 1) / k; // ceil(p / k)14 return hours;15}Step by step
- Feasibility: can we finish within h hours at speed k?
- The answer is between 1 and the largest pile.
- Find the first speed that works: keep mid if it works, else go right.
Complexity: O(n log max(pile)) time, O(1) space
Q&A
What interviewers ask once your code works, and problems to try on your own.
4.1Interview questions
Answer out loud, then open.
How do you avoid infinite loops?
How do you spot 'binary search on the answer'?
Why write mid as lo + (hi − lo) / 2?
4.2Solo practice
Try these without looking; open the hint only when stuck.
Hint
Use the first_true template with nums[mid] >= target.
Hint
Binary search the partition of the shorter array.
Extra depth
More fully worked problems in the same family, and the mistakes that cost offers.
5.12 more worked problems
Each one: the problem, the plan, the code and its cost.
Show detailsHide details
Search in Rotated Sorted Array
A sorted array was rotated. Find the target's index in O(log n).
- One half around mid is always sorted.
- If the target lies inside the sorted half, search there; otherwise search the other half.
1function search(nums: number[], target: number): number {2 let lo = 0, hi = nums.length - 1;3 while (lo <= hi) {4 const mid = (lo + hi) >> 1;5 if (nums[mid] === target) return mid;6 if (nums[lo] <= nums[mid]) {7 if (nums[lo] <= target && target < nums[mid]) hi = mid - 1;8 else lo = mid + 1;9 } else {10 if (nums[mid] < target && target <= nums[hi]) lo = mid + 1;11 else hi = mid - 1;12 }13 }14 return -1;15}Complexity: O(log n) time, O(1) space
Capacity To Ship Packages Within D Days
Packages ship in order. Find the smallest ship capacity that delivers everything within D days.
- Capacity is between the heaviest package and the total weight.
- A greedy pass tells you the days needed for a capacity; more capacity never needs more days.
- Binary search for the first capacity that fits.
1function shipWithinDays(weights: number[], days: number): number {2 const can = (cap: number) => {3 let need = 1, load = 0;4 for (const w of weights) {5 if (load + w > cap) {6 need++;7 load = 0;8 }9 load += w;10 }11 return need <= days;12 };13 let lo = Math.max(...weights), hi = weights.reduce((a, b) => a + b, 0);14 while (lo < hi) {15 const mid = Math.floor((lo + hi) / 2);16 if (can(mid)) hi = mid;17 else lo = mid + 1;18 }19 return lo;20}Complexity: O(n log(sum)) time, O(1) space
5.2Traps
Bugs and misreadings that come up again and again with this pattern.
Show detailsHide details
- Infinite loop from lo = mid
- Mixing inclusive and exclusive bounds
- Not proving the check is monotonic