Binary search pattern

Halve the search space, including the answer space.

Part 1 of 5

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.

Why it works

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.

Sorted or rotated array'Minimum X such that…' or 'maximum X such that…'A yes/no check that flips once (monotonic)Constraints up to 10⁹
Part 2 of 5

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.

Problem

Piles of bananas, h hours. Find the minimum eating speed k to finish in time.

Plan before you code

  1. Speed range is 1 to max(pile).
  2. Feasible(k): total hours = sum(ceil(p / k)) ≤ h. It is monotonic in k.
  3. Binary search for the first feasible speed.
Part 3 of 5

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

TypeScriptKotlinJava
first-value-where.tsTypeScriptCopy
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}
9 linesUTF-8TypeScript
first-value-where.ktKotlinCopy
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}
11 linesUTF-8Kotlin
first-value-where.javaJavaCopy
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}
9 linesUTF-8Java
  1. Loop until the range is a single value.
  2. If mid works, keep it and search left.
  3. Otherwise the answer is strictly to the right.

3.2Solution

Strict TypeScript, type-checked and tested.

Koko Eating Bananas

TypeScriptKotlinJava
koko-eating-bananas.tsTypeScriptCopy
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}
11 linesUTF-8TypeScript
koko-eating-bananas.ktKotlinCopy
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}
11 linesUTF-8Kotlin
koko-eating-bananas.javaJavaCopy
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}
15 linesUTF-8Java

Step by step

  1. Feasibility: can we finish within h hours at speed k?
  2. The answer is between 1 and the largest pile.
  3. Find the first speed that works: keep mid if it works, else go right.

Complexity: O(n log max(pile)) time, O(1) space

Part 4 of 5

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?
Pick one convention and keep it: with lo < hi, set hi = mid when mid works and lo = mid + 1 otherwise. The range then always shrinks.
How do you spot 'binary search on the answer'?
The question asks for a minimum or maximum value, and checking 'does value x work?' is easier than computing the answer directly.
Why write mid as lo + (hi − lo) / 2?
With fixed-size integers, lo + hi can overflow. TypeScript numbers are doubles, so it is safe there, but it is worth saying.

4.2Solo practice

Try these without looking; open the hint only when stuck.

EasyBinary Search
Hint

Use the first_true template with nums[mid] >= target.

HardMedian of Two Sorted Arrays
Hint

Binary search the partition of the shorter array.

Part 5 of 5

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
Medium

Search in Rotated Sorted Array

A sorted array was rotated. Find the target's index in O(log n).

  1. One half around mid is always sorted.
  2. If the target lies inside the sorted half, search there; otherwise search the other half.
search-rotated-sorted.tsTypeScriptCopy
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}
15 linesUTF-8TypeScript

Complexity: O(log n) time, O(1) space

Medium

Capacity To Ship Packages Within D Days

Packages ship in order. Find the smallest ship capacity that delivers everything within D days.

  1. Capacity is between the heaviest package and the total weight.
  2. A greedy pass tells you the days needed for a capacity; more capacity never needs more days.
  3. Binary search for the first capacity that fits.
capacity-ship-packages.tsTypeScriptCopy
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}
20 linesUTF-8TypeScript

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