Binary Search

How It Works

Binary search works on any search space where you can answer a yes/no question that splits the space into "definitely not here" and "maybe here" halves, most commonly a sorted array. Instead of scanning left to right, you repeatedly look at the middle element and use it to eliminate half the remaining candidates.

The core loop keeps two pointers, left and right, bounding the region that could still contain the answer. Each iteration computes mid, compares nums[mid] to the target, and moves one of the pointers past mid to shrink the window. Because the search space halves every iteration, you reach a single element (or an empty range) in O(log n) steps instead of O(n).

The pattern generalizes far beyond "find x in a sorted array." Any time a problem has a monotonic property, a condition that's false for a while and then flips to true (or vice versa) as some parameter increases, you can binary search on that parameter directly, even if there's no literal array involved (Koko Eating Bananas is a classic example: binary search over "eating speed").

When To Use It

• The array (or a transformation of it) is sorted, rotated-but-sorted, or otherwise monotonic.
• You need faster than linear time and the interviewer hints at "sorted input."
• You're searching for an exact value, the first/last occurrence of a value, or an insertion point.
• The array has been rotated at an unknown pivot; one half around mid is always still sorted, which is enough to decide which half to search.
• The problem asks you to minimize or maximize some value subject to a feasibility check: search on the answer space instead of the input array.

Time & Space Complexity

• Time: O(log n): the search space halves every iteration.
• Space: O(1) iterative implementation (recursive versions cost O(log n) stack space).

// Canonical binary search template
function binarySearch(nums, target) {
  let left = 0;
  let right = nums.length - 1;

  while (left <= right) {
    const mid = left + Math.floor((right - left) / 2); // avoids overflow
    if (nums[mid] === target) return mid;
    if (nums[mid] < target) left = mid + 1;
    else right = mid - 1;
  }

  return -1; // not found
}

Alternative Approaches

• Linear scan (O(n)): always correct, but ignores the sorted structure and is too slow once n gets large; use only to sanity-check before optimizing.
• Two pointers from both ends: useful for problems like "two sum in a sorted array," but doesn't generalize to rotated arrays or answer-space search the way binary search does.
• Built-in methods (Array.prototype.indexOf, sorted-set structures): fine in production code, but interviewers want to see you implement the halving logic yourself.

Common Mistakes

• Infinite loops from bad pointer updates: forgetting to move left/right past mid (e.g., left = mid instead of left = mid + 1) can loop forever.
• Off-by-one boundaries: mixing left < right and left <= right inconsistently with how mid is used causes the last element to be skipped or double-checked.
• Integer overflow mid-calculation: (left + right) / 2 isn't a real risk in JavaScript (no 32-bit int overflow the way it is in Java/C++), but writing left + Math.floor((right - left) / 2) is still the safer habit to carry between languages.
• Assuming the whole array is sorted after rotation: in rotated-array problems, only one side of mid is guaranteed sorted; you must check which side before deciding where the target could live.
• Binary searching an unsorted or non-monotonic space: the algorithm silently returns wrong answers if the underlying property isn't actually monotonic.

Pattern Summary

Binary search is the tool for any problem where the search space can be halved by a single comparison: sorted arrays, rotated sorted arrays, and "search on the answer" feasibility problems all reduce to the same left/right/mid template. Recognize monotonicity, define what "too small" and "too big" mean for your specific problem, and the rest is boilerplate.