How does binary search work, and what mathematical trick avoids integer overflow?

Short answer

On a pre-sorted array, binary search halves the search range at each step in O(log N). To prevent integer overflow when calculating the midpoint, use low + (high - low) / 2 instead of (low + high) / 2.

Explanation

If low and high are close to the maximum integer value (such as 2^31 - 1), adding them (low + high) causes integer overflow and becomes a negative number in languages such as Java and C++, potentially causing ArrayIndexOutOfBoundsException. Binary search can also be applied to a continuous answer space to solve optimization and minimax problems, not only to numeric arrays.

Code example

function binarySearch(arr: number[], target: number): number {
  let low = 0, high = arr.length - 1;
  while (low <= high) {
    const mid = low + Math.floor((high - low) / 2); // Safe from Overflow
    if (arr[mid] === target) return mid;
    if (arr[mid] < target) low = mid + 1;
    else high = mid - 1;
  }
  return -1;
}

Common mistakes

• Applying binary search to an unsorted array and expecting correct results.

Follow-up questions

• What are key bit-manipulation tricks, such as checking powers of two, counting set bits, and finding the unique element with XOR?

Sources

• Binary search algorithm - Wikipedia