/Projects
Coding patterns · 04 of 15

Binary search

Halve the search space, including the answer space.

PracticeCoding patternTier 2 · MechanismsApply15 minCore engineering

You will be able to: spot binary search from a problem statement, and code it from memory.

Interview prepCoding patterns

Study with AI

O(log n) per search; O(n log range) for search on the answer Watch as reels
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

first-value-where.tsTypeScript
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
  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

koko-eating-bananas.tsTypeScript
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

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.tsTypeScript
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.tsTypeScript
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
AI Engineer · Binary search