Lesson 12 of 2419 min read

Binary Search

Halve the search space every step. Easy to state, famously fiddly to write correctly, and far more widely applicable than "find a number in a sorted array".

By the end: Write binary search from memory, including searching on the answer.

The list is sorted. Look at the middle. If the target is smaller, the whole right half is irrelevant; if larger, the whole left half is. Repeat.

Every step throws away half of what remains, so a million items take about twenty steps. That is the power of O(log n), and it is why this shows up constantly.

Twenty steps to find one item in a million

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18function binarySearch(arr, target) {
  let lo = 0, hi = arr.length - 1, steps = 0;

  while (lo <= hi) {
    steps++;
    const mid = Math.floor((lo + hi) / 2);
    if (arr[mid] === target) return { index: mid, steps };
    if (arr[mid] < target) lo = mid + 1;    // target is to the right
    else hi = mid - 1;                       // target is to the left
  }
  return { index: -1, steps };
}

const million = Array.from({ length: 1000000 }, (_, i) => i * 2);
console.log('find 1999998:', binarySearch(million, 1999998));
console.log('find 0:      ', binarySearch(million, 0));
console.log('find missing:', binarySearch(million, 7));
console.log('a linear scan would take up to 1,000,000 steps');

Output

Pick one convention and never deviate

I recommend the inclusive form: hi is a real index, the loop runs while lo <= hi, and both sides always move past mid. Because both sides move, the range always shrinks, so it cannot loop forever.

The template. Learn this one shape.

1
2
3
4
5
6
7
8
9
10let lo = 0, hi = arr.length - 1;          // hi is INCLUSIVE

while (lo <= hi) {                        // so <= , not <
  const mid = Math.floor((lo + hi) / 2);

  if (arr[mid] === target) return mid;
  if (arr[mid] < target) lo = mid + 1;    // both sides move PAST mid
  else hi = mid - 1;
}
return -1;                                // lo is now the insertion point

The two classic infinite loops, demonstrated safely

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29// Bug 1: hi = mid instead of mid - 1, with an inclusive loop condition.
function buggyOne(arr, target) {
  let lo = 0, hi = arr.length - 1, guard = 0;
  while (lo <= hi) {
    if (++guard > 50) return 'INFINITE LOOP';
    const mid = Math.floor((lo + hi) / 2);
    if (arr[mid] === target) return mid;
    if (arr[mid] < target) lo = mid + 1;
    else hi = mid;                          // never shrinks when lo === hi
  }
  return -1;
}

// Bug 2: lo = mid instead of mid + 1.
function buggyTwo(arr, target) {
  let lo = 0, hi = arr.length - 1, guard = 0;
  while (lo <= hi) {
    if (++guard > 50) return 'INFINITE LOOP';
    const mid = Math.floor((lo + hi) / 2);
    if (arr[mid] === target) return mid;
    if (arr[mid] < target) lo = mid;         // stuck when hi === lo + 1
    else hi = mid - 1;
  }
  return -1;
}

console.log('buggy hi = mid:', buggyOne([1, 3, 5], 2));
console.log('buggy lo = mid:', buggyTwo([1, 3, 5], 4));
console.log('correct version returns -1 for both, quickly');

Output

The version you actually need most: boundaries

Plain "find the target" is the least useful variant. Real questions ask for the first position satisfying a condition: the first element not less than x, the leftmost occurrence, the insertion point. That is lowerBound, and it is worth knowing cold.

lowerBound and upperBound

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30// First index where arr[i] >= target. Returns arr.length if none.
function lowerBound(arr, target) {
  let lo = 0, hi = arr.length;          // hi is EXCLUSIVE here
  while (lo < hi) {                     // so < , not <=
    const mid = Math.floor((lo + hi) / 2);
    if (arr[mid] < target) lo = mid + 1;
    else hi = mid;                      // keep mid as a candidate
  }
  return lo;
}

// First index where arr[i] > target.
function upperBound(arr, target) {
  let lo = 0, hi = arr.length;
  while (lo < hi) {
    const mid = Math.floor((lo + hi) / 2);
    if (arr[mid] <= target) lo = mid + 1;
    else hi = mid;
  }
  return lo;
}

const a = [1, 2, 2, 2, 3, 5, 5, 8];
console.log('array:', a);
console.log('lowerBound(2) =', lowerBound(a, 2), '← first 2');
console.log('upperBound(2) =', upperBound(a, 2), '← just past the last 2');
console.log('count of 2s   =', upperBound(a, 2) - lowerBound(a, 2));
console.log('lowerBound(4) =', lowerBound(a, 4), '← insertion point for 4');
console.log('lowerBound(9) =', lowerBound(a, 9), '← past the end');
console.log('lowerBound(0) =', lowerBound(a, 0), '← before everything');

Output

First and last occurrence, built from the bounds

1
2
3
4
5
6
7
8
9
10
11
12
13function lowerBound(arr, t) { let lo = 0, hi = arr.length; while (lo < hi) { const m = (lo + hi) >> 1; arr[m] < t ? lo = m + 1 : hi = m; } return lo; }
function upperBound(arr, t) { let lo = 0, hi = arr.length; while (lo < hi) { const m = (lo + hi) >> 1; arr[m] <= t ? lo = m + 1 : hi = m; } return lo; }

function searchRange(arr, target) {
  const first = lowerBound(arr, target);
  if (first === arr.length || arr[first] !== target) return [-1, -1];
  return [first, upperBound(arr, target) - 1];
}

console.log(searchRange([5, 7, 7, 8, 8, 10], 8));   // [3,4]
console.log(searchRange([5, 7, 7, 8, 8, 10], 6));   // [-1,-1]
console.log(searchRange([], 0));                     // [-1,-1]
console.log(searchRange([1], 1));                    // [0,0]

Output

Binary search on the answer

This is the technique that separates people who have memorised binary search from people who understand it. The array does not have to exist. If you can ask a yes/no question about a candidate answer, and the answers are monotonic — once it becomes true it stays true — then you can binary search the answer space.

Square root, without Math.sqrt

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16// Find the largest k with k*k <= n. The predicate "k*k <= n" is monotonic:
// true for small k, false for large k. So binary search for the boundary.
function isqrt(n) {
  if (n < 2) return n;
  let lo = 1, hi = n, answer = 1;
  while (lo <= hi) {
    const mid = Math.floor((lo + hi) / 2);
    if (mid * mid <= n) { answer = mid; lo = mid + 1; }   // feasible: try bigger
    else hi = mid - 1;                                     // too big
  }
  return answer;
}

for (const n of [0, 1, 4, 8, 16, 24, 2147395600]) {
  console.log(`isqrt(${n}) = ${isqrt(n)}`);
}

Output

Minimum eating speed: the canonical answer-space search

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18// Piles of bananas, h hours available. Eating speed k per hour means pile p
// takes ceil(p / k) hours. Find the smallest k that finishes in time.
function minEatingSpeed(piles, h) {
  const hoursNeeded = (k) => piles.reduce((sum, p) => sum + Math.ceil(p / k), 0);

  let lo = 1, hi = Math.max(...piles);      // speed 1 is slowest, max is fastest useful
  while (lo < hi) {
    const mid = Math.floor((lo + hi) / 2);
    if (hoursNeeded(mid) <= h) hi = mid;    // feasible: this might be the answer
    else lo = mid + 1;                      // too slow
  }
  return lo;
}

console.log(minEatingSpeed([3, 6, 7, 11], 8));          // 4
console.log(minEatingSpeed([30, 11, 23, 4, 20], 5));    // 30
console.log(minEatingSpeed([30, 11, 23, 4, 20], 6));    // 23
console.log(minEatingSpeed([1], 1));                     // 1

Output

Notice the structure: a feasible(candidate) function, a known range, and a binary search for the boundary. Once you see it, a dozen apparently different problems become the same problem with a different feasible.

Split an array into k parts, minimising the largest part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25function splitArray(nums, k) {
  // Can we do it with no part exceeding `limit`? Greedy: fill parts in order.
  const canDo = (limit) => {
    let parts = 1, current = 0;
    for (const x of nums) {
      if (x > limit) return false;
      if (current + x > limit) { parts++; current = x; }
      else current += x;
    }
    return parts <= k;
  };

  let lo = Math.max(...nums);                       // no part can be smaller than this
  let hi = nums.reduce((a, b) => a + b, 0);         // one part holding everything
  while (lo < hi) {
    const mid = Math.floor((lo + hi) / 2);
    if (canDo(mid)) hi = mid;
    else lo = mid + 1;
  }
  return lo;
}

console.log(splitArray([7, 2, 5, 10, 8], 2));    // 18
console.log(splitArray([1, 2, 3, 4, 5], 2));     // 9
console.log(splitArray([1, 4, 4], 3));           // 4

Output

Rotated arrays

A sorted array rotated at an unknown point is still searchable in O(log n), because at least one half of any range is properly sorted, and you can tell which by comparing the ends.

Search in a rotated sorted array

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22function searchRotated(nums, target) {
  let lo = 0, hi = nums.length - 1;
  while (lo <= hi) {
    const mid = Math.floor((lo + hi) / 2);
    if (nums[mid] === target) return mid;

    if (nums[lo] <= nums[mid]) {
      // Left half is sorted. Is the target inside it?
      if (nums[lo] <= target && target < nums[mid]) hi = mid - 1;
      else lo = mid + 1;
    } else {
      // Right half is sorted.
      if (nums[mid] < target && target <= nums[hi]) lo = mid + 1;
      else hi = mid - 1;
    }
  }
  return -1;
}

const rotated = [4, 5, 6, 7, 0, 1, 2];
for (const t of [0, 4, 2, 3]) console.log(`search ${t}:`, searchRotated(rotated, t));
console.log('single element:', searchRotated([1], 1), searchRotated([1], 0));

Output

Find the minimum of a rotated array

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15function findMin(nums) {
  let lo = 0, hi = nums.length - 1;
  while (lo < hi) {
    const mid = Math.floor((lo + hi) / 2);
    // If mid is greater than the last element, the rotation point is to the right.
    if (nums[mid] > nums[hi]) lo = mid + 1;
    else hi = mid;               // mid could be the minimum, so keep it
  }
  return nums[lo];
}

console.log(findMin([3, 4, 5, 1, 2]));       // 1
console.log(findMin([4, 5, 6, 7, 0, 1, 2])); // 0
console.log(findMin([11, 13, 15, 17]));      // 11, not rotated
console.log(findMin([2, 1]));                 // 1

Output

Two dimensions and two arrays

Search a row-sorted, column-sorted matrix

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25// Each row is sorted left to right, each column top to bottom.
// Start at the top-right: too big means go left, too small means go down.
// O(rows + cols), which beats binary searching every row.
function searchMatrix(matrix, target) {
  if (matrix.length === 0) return false;
  let r = 0, c = matrix[0].length - 1;
  const path = [];
  while (r < matrix.length && c >= 0) {
    path.push(`(${r},${c})=${matrix[r][c]}`);
    if (matrix[r][c] === target) { console.log('  path:', path.join(' → ')); return true; }
    if (matrix[r][c] > target) c--;
    else r++;
  }
  console.log('  path:', path.join(' → '));
  return false;
}

const matrix = [
  [1, 4, 7, 11],
  [2, 5, 8, 12],
  [3, 6, 9, 16],
  [10, 13, 14, 17],
];
console.log('find 5:', searchMatrix(matrix, 5));
console.log('find 20:', searchMatrix(matrix, 20));

Output

Your turn: five binary searches

searchInsert(nums, target) — the index of the target, or where it would be inserted. This is lowerBound.
firstBadVersion(n, isBad) — versions 1..n, all bad from some point on. Find the first bad one with the fewest calls to isBad.
peakIndex(nums) — the array rises then falls; find the peak in O(log n). Compare nums[mid] with nums[mid+1].
shipWithinDays(weights, days) — minimum ship capacity to send all packages in order within days. Answer-space search with a greedy check.
findMedianSortedArrays(a, b) — the hard one. The median of two sorted arrays in O(log(min(m,n))). Binary search the split point of the shorter array. Try it; the O(m+n) merge is a fine fallback.

Editable. Fill them in, then run.

function searchInsert(nums, target) {
  // lowerBound
}

function firstBadVersion(n, isBad) {
  // lo = 1, hi = n, keep mid when isBad(mid)
}

function peakIndex(nums) {
  // if nums[mid] < nums[mid+1] the peak is to the right
}

function shipWithinDays(weights, days) {
  // lo = max weight, hi = total; feasible(capacity) counts days greedily
}

function findMedianSortedArrays(a, b) {
  // start with the simple merge; then try the log version
}

console.log(searchInsert([1, 3, 5, 6], 5), searchInsert([1, 3, 5, 6], 2));   // 2 1
console.log(firstBadVersion(5, (v) => v >= 4));                              // 4
console.log(peakIndex([1, 3, 5, 4, 2]));                                     // 2
console.log(peakIndex([1, 2, 3]));                                           // 2
console.log(shipWithinDays([1,2,3,4,5,6,7,8,9,10], 5));                      // 15
console.log(shipWithinDays([3,2,2,4,1,4], 3));                               // 6
console.log(findMedianSortedArrays([1, 3], [2]));                            // 2
console.log(findMedianSortedArrays([1, 2], [3, 4]));                         // 2.5

Output

Recap

Binary search halves the range each step, so a million items take about twenty comparisons.
Pick one convention and hold it: inclusive hi with lo <= hi and both sides moving past mid, or exclusive hi with lo < hi and hi = mid. Mixing them causes infinite loops.
lowerBound — the first index not less than the target — is more useful than plain search, and gives you counts, ranges and insertion points.
When a problem asks for a minimum or maximum value and checking a candidate is easy, binary search the answer using a monotonic feasible() predicate.
In a rotated array one half is always sorted; compare against the end to work out which.

Pick one convention and never deviate

The version you actually need most: boundaries

Binary search on the answer

Rotated arrays

Two dimensions and two arrays

Your turn: five binary searches

Recap

New writing, when it lands.