Binary Search on the Answer

Searching for the answer itself

Lesson 28 ended with a general idea: binary search finds the first point where a yes/no question changes from false to true. Binary search is a method that checks the middle of a range and throws away half of the range each time. Until now the question was about array positions. In this lesson the question is about candidate answers (possible answers that we want to test).

Example: “What is the slowest eating speed that finishes all the bananas in 8 hours?” Working out that speed directly is hard. But checking a guess is easy. At speed 5, add up the hours. And if speed 5 works, speed 6 works too. So the question “does speed k work?” is false for small k and true for large k. This is exactly the shape that binary search needs.

Recognising the pattern

Look for these three signs in the problem:

• It asks for a minimum or maximum value: the smallest speed, the least capacity, the largest distance.
• For a given guess, you can check whether it works in about O(n) time. Often this is a simple greedy pass. A greedy method always takes the best choice it can see right now, and never goes back.
• The answer is monotonic. This means the results only change in one direction: if x works, every larger x works too (or every smaller x works).

The four-step recipe

The time is O(n · log(range)). There are about log(range) guesses, and each guess is checked in O(n) time. Even a range of 10⁹ needs only about 30 guesses.

A first example: integer square root

The integer square root of x is the largest whole number r with r × r ≤ x. For example, it is 2 for x = 8. The test “r × r > x” is false for small r and true for large r. Find the first r where it is true. The answer is one less than that r.

function mySqrt(x) {  // the last r with r * r <= x  =  (the first r with r * r > x) - 1  let lo = 0, hi = x + 1;  while (lo < hi) {    const mid = lo + Math.floor((hi - lo) / 2);    if (mid * mid > x) hi = mid;    else lo = mid + 1;  }  return lo - 1;}console.log(mySqrt(8));  // 2   (2 × 2 = 4 ≤ 8, 3 × 3 = 9 > 8)console.log(mySqrt(16)); // 4console.log(mySqrt(0));  // 0

Minimum speed: Koko eating bananas

Koko has piles of bananas and h hours. At speed k she eats up to k bananas per hour, from one pile only. A pile of 7 at speed 3 takes 3 hours (3 + 3 + 1 bananas). Find the slowest speed that finishes in time.

• Range: 1 to the largest pile. At that speed, every pile takes exactly 1 hour.
• Check: total hours = the sum of Math.ceil(pile / k) (Math.ceil rounds up). The speed works if the total is ≤ h.
• Direction: a faster speed never takes longer, so the answers are false…false, true…true. Find the first true.

Traced: finding Koko's speed

1const piles = [3, 6, 7, 11], h = 8;2const hours = (k) => piles.reduce((t, p) => t + Math.ceil(p / k), 0);▶let lo = 1, hi = Math.max(...piles);4while (lo < hi) {5  const mid = lo + Math.floor((hi - lo) / 2);6  if (hours(mid) <= h) hi = mid;7  else lo = mid + 1;8}9console.log(lo);

Minimum capacity and the greedy check

Packages must be shipped in the given order within a number of days. What is the smallest ship capacity (the most weight the ship can carry in one day) that works? The check is greedy: load packages in order, and start a new day only when the next package does not fit. Loading as much as possible each day never needs more days than any other way of loading.

function shipWithinDays(weights, days) {  // Greedy check: load packages in order. Start a new day when the next one does not fit.  const daysNeeded = (cap) => {    let d = 1, load = 0;    for (const w of weights) {      if (load + w > cap) { d++; load = 0; }      load += w;    }    return d;  };  let lo = Math.max(...weights);                     // must fit the heaviest package  let hi = weights.reduce((a, b) => a + b, 0);        // everything in one day  while (lo < hi) {    const mid = lo + Math.floor((hi - lo) / 2);    if (daysNeeded(mid) <= days) hi = mid;    else lo = mid + 1;  }  return lo;}console.log(shipWithinDays([1, 2, 3, 4, 5, 6, 7, 8, 9, 10], 5)); // 15

The lower end of the range matters. The capacity must be at least the weight of the heaviest package, or that package could never be shipped. “Split an array into k parts so that the largest sum is as small as possible” is the same problem in different words (Practice question 5).

Maximising the minimum

Some problems ask for the largest value that works. An example is the largest possible smallest gap when you place balls in baskets. Now works(x) gives true…true, false…false, and you want the last true. Make two changes. First, set lo = mid when mid works. Second, round mid up, so that the range always gets smaller.

// Place m balls in baskets at the given positions so the smallest gap is as large as possible.function maxDistance(position, m) {  const pos = [...position].sort((a, b) => a - b);  const canPlace = (gap) => {                 // greedy: put each ball as far left as allowed    let count = 1, last = pos[0];    for (const p of pos) {      if (p - last >= gap) { count++; last = p; }    }    return count >= m;  };  // canPlace is true…true, false…false — find the LAST true  let lo = 1, hi = pos[pos.length - 1] - pos[0];  while (lo < hi) {    const mid = lo + Math.ceil((hi - lo) / 2);  // round UP, or lo = mid could make an endless loop    if (canPlace(mid)) lo = mid;    else hi = mid - 1;  }  return lo;}console.log(maxDistance([1, 2, 3, 4, 7], 3)); // 3   (balls at 1, 4, 7)

Practice questions

For every question, write the four recipe steps as comments before you write any code.

function mySqrt(x) {  let lo = 0, hi = x;  while (lo < hi) {    const mid = lo + Math.ceil((hi - lo) / 2);    if (mid * mid <= x) lo = mid;    else hi = mid - 1;  }  return lo;}console.log(mySqrt(4));          // 2console.log(mySqrt(8));          // 2console.log(mySqrt(2147395599)); // 46339

function minEatingSpeed(piles, h) {  let lo = 1, hi = Math.max(...piles);  while (lo < hi) {    const k = lo + Math.floor((hi - lo) / 2);    let hours = 0;    for (const p of piles) hours += Math.ceil(p / k);    if (hours <= h) hi = k;    else lo = k + 1;  }  return lo;}console.log(minEatingSpeed([3, 6, 7, 11], 8));        // 4console.log(minEatingSpeed([30, 11, 23, 4, 20], 5));  // 30

function smallestDivisor(nums, threshold) {  let lo = 1, hi = Math.max(...nums);  while (lo < hi) {    const d = lo + Math.floor((hi - lo) / 2);    const sum = nums.reduce((s, x) => s + Math.ceil(x / d), 0);    if (sum <= threshold) hi = d;    else lo = d + 1;  }  return lo;}console.log(smallestDivisor([1, 2, 5, 9], 6)); // 5

function shipWithinDays(weights, days) {  const need = (cap) => {    let d = 1, load = 0;    for (const w of weights) {      if (load + w > cap) { d++; load = 0; }      load += w;    }    return d;  };  let lo = Math.max(...weights), hi = weights.reduce((a, b) => a + b, 0);  while (lo < hi) {    const mid = lo + Math.floor((hi - lo) / 2);    if (need(mid) <= days) hi = mid;    else lo = mid + 1;  }  return lo;}console.log(shipWithinDays([1, 2, 3, 4, 5, 6, 7, 8, 9, 10], 5)); // 15console.log(shipWithinDays([3, 2, 2, 4, 1, 4], 3));              // 6

function splitArray(nums, k) {  const parts = (limit) => {    let p = 1, sum = 0;    for (const x of nums) {      if (sum + x > limit) { p++; sum = 0; }      sum += x;    }    return p;  };  let lo = Math.max(...nums), hi = nums.reduce((a, b) => a + b, 0);  while (lo < hi) {    const mid = lo + Math.floor((hi - lo) / 2);    if (parts(mid) <= k) hi = mid;    else lo = mid + 1;  }  return lo;}console.log(splitArray([7, 2, 5, 10, 8], 2)); // 18console.log(splitArray([1, 2, 3, 4, 5], 2));  // 9

function maxDistance(position, m) {  const pos = [...position].sort((a, b) => a - b);  const canPlace = (gap) => {    let count = 1, last = pos[0];    for (const p of pos) if (p - last >= gap) { count++; last = p; }    return count >= m;  };  let lo = 1, hi = pos[pos.length - 1] - pos[0];  while (lo < hi) {    const mid = lo + Math.ceil((hi - lo) / 2);    if (canPlace(mid)) lo = mid;    else hi = mid - 1;  }  return lo;}console.log(maxDistance([1, 2, 3, 4, 7], 3));                  // 3console.log(maxDistance([5, 4, 3, 2, 1, 1000000000], 2));      // 999999999

Make it stick

Part 6 complete — what's next

You can now use binary search on arrays, boundaries, rotated arrays and answers. When a problem says “sorted”, “minimum that works” or O(log n), think of this part.

Part 7 — Strings uses the techniques you know (two pointers, windows and frequency maps) on text: palindromes, prefixes, Roman numerals, compression and substring windows.