Binary Search on a Sorted Array

Halve the search space every step

Think of a number between 1 and 100, and I will guess it. After each guess you only say “higher” or “lower”. The best plan is to guess the middle each time: 50, then 25 or 75, and so on. Every answer removes half of the remaining possibilities. So 7 guesses are always enough (2⁷ = 128, which is more than 100).

Binary search is a method that finds a value in a sorted array by checking the middle item and throwing away half of the array each time. Compare the target with the middle item. If the middle item is too small, the target can only be in the right half. If it is too big, the target can only be in the left half. Halving again and again (the loop from Lesson 12) makes the time O(log n). This means about 20 steps for a million items and about 30 steps for a billion items. (log n is the number of times you can halve n until you reach 1.)

The binary search template

Keep two indices (positions), lo and hi. They mark the range where the target could still be. Each step looks at the middle and throws away the half that cannot contain the target.

function binarySearch(nums, target) {  let lo = 0, hi = nums.length - 1;          // search the closed range [lo, hi]  while (lo <= hi) {                          // non-empty while lo <= hi    const mid = lo + Math.floor((hi - lo) / 2);    if (nums[mid] === target) return mid;    if (nums[mid] < target) lo = mid + 1;     // mid is ruled out, so skip it    else hi = mid - 1;  }  return -1;}console.log(binarySearch([-1, 0, 3, 5, 9, 12], 9)); // 4console.log(binarySearch([-1, 0, 3, 5, 9, 12], 2)); // -1

Traced: searching for 9

1const nums = [1, 3, 5, 7, 9, 11, 13];2const target = 9;▶let lo = 0, hi = nums.length - 1;4while (lo <= hi) {5  const mid = Math.floor((lo + hi) / 2);6  if (nums[mid] === target) break;7  if (nums[mid] < target) lo = mid + 1;8  else hi = mid - 1;9}10console.log(lo <= hi ? "found" : "missing");

Infinite loops and off-by-one errors

Binary search is short, but it is easy to get wrong. An off-by-one error means a boundary is wrong by exactly one position. An infinite loop is a loop that never ends. Most bugs come from mixing two styles. Choose one style and keep its three parts (start, loop condition, moves) consistent. A closed range [lo, hi] includes both ends. A half-open range [lo, hi) includes lo but not hi.

Writing lo + Math.floor((hi - lo) / 2) instead of (lo + hi) / 2 avoids overflow. Overflow means a number gets too big for the space that holds it. It happens in languages with fixed-size integers, such as Java or C++. JavaScript numbers do not overflow at this size, but many programmers use this habit and interviewers recognise it.

Lower bound and upper bound

Often you do not need “is it there?”. You need “where does it start?”. The lower bound is the first index whose value is ≥ target. The upper bound is the first index whose value is > target. Both use the half-open style. When mid might be the answer, keep it with hi = mid.

// First index i with nums[i] >= target (nums.length if none).function lowerBound(nums, target) {  let lo = 0, hi = nums.length;               // half-open range [lo, hi)  while (lo < hi) {    const mid = lo + Math.floor((hi - lo) / 2);    if (nums[mid] < target) lo = mid + 1;     // mid is too small, so the answer is right of it    else hi = mid;                            // mid might be the answer, so keep it  }  return lo;}// First index i with nums[i] > target.function upperBound(nums, target) {  let lo = 0, hi = nums.length;  while (lo < hi) {    const mid = lo + Math.floor((hi - lo) / 2);    if (nums[mid] <= target) lo = mid + 1;    else hi = mid;  }  return lo;}const a = [1, 2, 2, 2, 5, 7];console.log(lowerBound(a, 2), upperBound(a, 2)); // 1 4console.log(lowerBound(a, 3), upperBound(a, 3)); // 4 4   (3 would be inserted at 4)console.log(upperBound(a, 2) - lowerBound(a, 2)); // 3   how many 2s

The lower bound is also the answer to “search insert position”. This is the index where the value would go to keep the array sorted.

First and last occurrence

When the array has duplicates, the first occurrence of x is at lowerBound(x) (check that this index really holds x). The last occurrence is at upperBound(x) − 1. The count of x is upperBound(x) − lowerBound(x). This uses two O(log n) searches instead of an O(n) scan.

The general idea: find the first “true”

Lower bound and upper bound are the same algorithm with a different test. A predicate is a function that answers yes or no (true or false). Binary search works whenever a predicate about index i is false for a while and then true for the rest, like false, false, false, true, true. Binary search finds the first true:

// The first index where check(i) becomes true, when check gives false…false, true…true.function firstTrue(lo, hi, check) {          // searches [lo, hi); returns hi if never true  while (lo < hi) {    const mid = lo + Math.floor((hi - lo) / 2);    if (check(mid)) hi = mid;    else lo = mid + 1;  }  return lo;}const nums = [1, 2, 2, 2, 5, 7];console.log(firstTrue(0, nums.length, (i) => nums[i] >= 2)); // 1   lower bound of 2console.log(firstTrue(0, nums.length, (i) => nums[i] > 2));  // 4   upper bound of 2

This view makes binary search very powerful. The “array” does not even need to exist. Lesson 29 searches over possible answers instead of indices.

Rotated sorted arrays

A rotated sorted array is a sorted array whose front part was moved to the back, at a point you do not know. An example is [4, 5, 6, 7, 0, 1, 2]. The whole array is not sorted. But when you cut it at any mid, at least one half is sorted (this lesson assumes all values are different). Check which half is sorted by comparing nums[lo] with nums[mid]. If the target lies inside the range of that sorted half, search that half. Otherwise search the other half.

function search(nums, target) {  let lo = 0, hi = nums.length - 1;  while (lo <= hi) {    const mid = lo + Math.floor((hi - lo) / 2);    if (nums[mid] === target) return mid;    if (nums[lo] <= nums[mid]) {                        // left half lo..mid is sorted      if (nums[lo] <= target && target < nums[mid]) hi = mid - 1;      else lo = mid + 1;    } else {                                            // right half mid..hi is sorted      if (nums[mid] < target && target <= nums[hi]) lo = mid + 1;      else hi = mid - 1;    }  }  return -1;}console.log(search([4, 5, 6, 7, 0, 1, 2], 0)); // 4console.log(search([4, 5, 6, 7, 0, 1, 2], 3)); // -1

Practice questions

For each question, first write the yes/no test that changes from false to true. The code then follows from it.

function search(nums, target) {  let lo = 0, hi = nums.length - 1;  while (lo <= hi) {    const mid = lo + Math.floor((hi - lo) / 2);    if (nums[mid] === target) return mid;    if (nums[mid] < target) lo = mid + 1;    else hi = mid - 1;  }  return -1;}console.log(search([-1, 0, 3, 5, 9, 12], 9)); // 4console.log(search([-1, 0, 3, 5, 9, 12], 2)); // -1

function searchInsert(nums, target) {  let lo = 0, hi = nums.length;  while (lo < hi) {    const mid = lo + Math.floor((hi - lo) / 2);    if (nums[mid] < target) lo = mid + 1;    else hi = mid;  }  return lo;}console.log(searchInsert([1, 3, 5, 6], 5)); // 2console.log(searchInsert([1, 3, 5, 6], 2)); // 1console.log(searchInsert([1, 3, 5, 6], 7)); // 4

function searchRange(nums, target) {  const i = nums.indexOf(target);  if (i === -1) return [-1, -1];  let j = i;  while (j + 1 < nums.length && nums[j + 1] === target) j++;  return [i, j];}console.log(searchRange([5, 7, 7, 8, 8, 10], 8)); // [ 3, 4 ]

function searchRange(nums, target) {  const bound = (strict) => {    let lo = 0, hi = nums.length;    while (lo < hi) {      const mid = lo + Math.floor((hi - lo) / 2);      if (nums[mid] < target || (strict && nums[mid] === target)) lo = mid + 1;      else hi = mid;    }    return lo;  };  const first = bound(false);  if (first === nums.length || nums[first] !== target) return [-1, -1];  return [first, bound(true) - 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 ]

function firstBadVersion(n, isBad) {  let lo = 1, hi = n;  while (lo < hi) {    const mid = lo + Math.floor((hi - lo) / 2);    if (isBad(mid)) hi = mid;      // mid might be the first bad one    else lo = mid + 1;             // mid is good: the first bad one is later  }  return lo;}console.log(firstBadVersion(5, (v) => v >= 4));          // 4console.log(firstBadVersion(2126753390, (v) => v >= 1702766719)); // 1702766719

function search(nums, target) {  let lo = 0, hi = nums.length - 1;  while (lo <= hi) {    const mid = lo + Math.floor((hi - lo) / 2);    if (nums[mid] === target) return mid;    if (nums[lo] <= nums[mid]) {      if (nums[lo] <= target && target < nums[mid]) hi = mid - 1;      else lo = mid + 1;    } else {      if (nums[mid] < target && target <= nums[hi]) lo = mid + 1;      else hi = mid - 1;    }  }  return -1;}console.log(search([4, 5, 6, 7, 0, 1, 2], 0)); // 4console.log(search([4, 5, 6, 7, 0, 1, 2], 3)); // -1console.log(search([1], 0));                   // -1

function findMin(nums) {  let lo = 0, hi = nums.length - 1;  while (lo < hi) {    const mid = lo + Math.floor((hi - lo) / 2);    if (nums[mid] > nums[hi]) lo = mid + 1;   // minimum is strictly right of mid    else hi = mid;                            // mid could be the minimum  }  return nums[lo];}console.log(findMin([3, 4, 5, 1, 2]));       // 1console.log(findMin([4, 5, 6, 7, 0, 1, 2])); // 0console.log(findMin([11, 13, 15, 17]));      // 11

function findPeakElement(nums) {  let lo = 0, hi = nums.length - 1;  while (lo < hi) {    const mid = lo + Math.floor((hi - lo) / 2);    if (nums[mid] < nums[mid + 1]) lo = mid + 1;   // rising: a peak is to the right    else hi = mid;                                 // falling: mid or something left is a peak  }  return lo;}console.log(findPeakElement([1, 2, 3, 1]));          // 2console.log(findPeakElement([1, 2, 1, 3, 5, 6, 4])); // 5

Make it stick

What's next

Lesson 29 uses the “first true” idea on answers: the smallest speed, the smallest capacity, the largest minimum. Sometimes checking a guess is easy, but finding the answer directly is hard. Then binary search on the answer often solves the problem.