How do you implement binary search, and what are the common bugs?

Think of finding a word in a printed dictionary. You do not start at page 1. You open somewhere in the middle, see that your word comes later, and ignore the whole first half. Then you open the middle of what is left, and so on. Each step throws away half the remaining pages, so even a 1,000-page dictionary needs only about 10 steps.

Binary search does exactly this on a sorted array. If the array is not sorted, the "throw away half" step is not safe, and the method does not work.

function binarySearch(arr, target) {
  let low = 0;
  let high = arr.length - 1; // inclusive: high is a valid index

  while (low <= high) { // <= so a one-element range is still checked
    const mid = low + Math.floor((high - low) / 2); // overflow-safe middle
    if (arr[mid] === target) {
      return mid; // found it
    } else if (arr[mid] < target) {
      low = mid + 1; // target is to the right; mid is already ruled out
    } else {
      high = mid - 1; // target is to the left; mid is already ruled out
    }
  }
  return -1; // low crossed high, target is not present
}

const nums = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91];
console.log(binarySearch(nums, 23)); // Output: 5
console.log(binarySearch(nums, 2)); // Output: 0
console.log(binarySearch(nums, 91)); // Output: 9
console.log(binarySearch(nums, 7)); // Output: -1
console.log(binarySearch([], 4)); // Output: -1

Tracing the search for 23:

• low = 0, high = 9, mid = 4, arr[4] = 16 < 23, so low = 5.
• low = 5, high = 9, mid = 7, arr[7] = 56 > 23, so high = 6.
• low = 5, high = 6, mid = 5, arr[5] = 23. Found at index 5.

Three comparisons instead of six for a linear scan, and the gap grows quickly with bigger arrays.

The loop keeps one promise, called the invariant: if the target is in the array, it is somewhere between low and high, inclusive. Every update keeps that promise true while shrinking the range. When low > high, the range is empty, so the target is not there.

Why the overflow-safe mid? In Java, C++ or C, low and high are 32-bit integers. If both are above about 1.07 billion, low + high exceeds the largest int (2,147,483,647) and wraps around to a negative number, giving a negative index. low + (high - low) / 2 gives the same middle without ever adding two large numbers. JavaScript numbers do not overflow at this size, but interviewers expect you to write it this way anyway.

int mid = low + (high - low) / 2;   // safe
// int mid = (low + high) / 2;      // can overflow for very large arrays

For an array of 10 lakh (1,000,000) elements, binary search needs at most 20 comparisons, because 2^20 is just over a million.

• Using low < high with an inclusive high. When the range shrinks to one element, the loop stops without checking it.
• Writing low = mid or high = mid. If mid is already ruled out and you do not move past it, the range can stop shrinking and the loop runs forever.
• (low + high) / 2 in Java or C++, which overflows for huge arrays.
• Forgetting Math.floor in JavaScript, which gives a fractional index like 4.5.
• Running it on unsorted data.
• Mixing the two styles: inclusive high = n - 1 goes with low <= high and high = mid - 1; exclusive high = n goes with low < high and high = mid. Pick one and stay consistent.

• How do you find the first or last occurrence of a value that appears many times?
• How do you search in a rotated sorted array?
• How would you find the square root of a number using binary search?
• What is "binary search on the answer"?