Modified Binary Search Pattern

When to use Modified Binary Search

• The input is sorted but rotated, or has a single "pivot" or peak you need to locate.
• The input is sorted but you don't know its length up front (infinite array problems).
• The input is a 2D matrix whose rows and/or columns are sorted.
• You are searching over an answer-space ("smallest k that satisfies P") and P is monotonic in k.
• You need to find the leftmost or rightmost occurrence of a value in a sorted array with duplicates.

Template

function binarySearch(nums, target) {
  let left = 0;
  let right = nums.length - 1;
  while (left <= right) {
    const mid = left + Math.floor((right - left) / 2);
    if (nums[mid] === target) {
      return mid;
    } else if (nums[mid] < target) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }
  return -1;
}

Common mistakes

• Computing `mid = (left + right) / 2` and overflowing on 32-bit integers; use `left + (right - left) / 2` instead.
• Using `left < right` vs `left <= right` without matching the rest of the loop — the two styles produce subtly different post-conditions.
• On rotated arrays, deciding which half is sorted using the wrong comparison and recursing into the unsorted half.
• Forgetting to update `left` or `right` to `mid` (instead of `mid + 1` / `mid - 1`) in answer-space searches, causing infinite loops.
• Returning the index instead of the value (or vice versa) on the recursive-base case.