Binary Search

Explanation

Binary search works by maintaining a [left, right] search window. At each step, it checks the middle element: if it equals the target, return; if it's less than the target, the target must be in the right half (left = mid + 1); if it's greater, the target must be in the left half (right = mid - 1). Each comparison eliminates half the remaining candidates, giving O(log n) comparisons for n elements — 1 billion elements require at most 30 comparisons. The catch: binary search only works on sorted data. The O(log n) speedup is meaningless if you have to sort first (O(n log n)), unless you're searching the same sorted array many times. For a single search on unsorted data, linear search is fine. For k searches on the same sorted data, binary search's O(k log n) beats linear search's O(k*n) for large k. Beyond "find an exact value," binary search variants solve many related problems: find the leftmost position where a condition becomes true (lower bound), find the rightmost position where a condition is still true (upper bound), find the minimum x where f(x) is true (binary search on a monotonic function). The last pattern is surprisingly powerful — you can binary search on almost anything if you can define a monotonic predicate. The implementation is notoriously error-prone. The classic bugs are infinite loops from wrong loop termination conditions, off-by-one errors in left/right updates, and integer overflow in mid computation (use left + Math.floor((right - left) / 2) instead of Math.floor((left + right) / 2) in languages with integer overflow).

Code Example

// Binary search — iterative (standard and "find leftmost")

// Standard: returns index of target, or -1 if not found
function binarySearch(arr, target) {
  let left = 0, right = arr.length - 1;
  while (left <= right) {
    const mid = left + Math.floor((right - left) / 2);
    if (arr[mid] === target) return mid;
    if (arr[mid] < target)   left = mid + 1;
    else                     right = mid - 1;
  }
  return -1;
}

// Lower bound: first index where arr[i] >= target
function lowerBound(arr, target) {
  let left = 0, right = arr.length;
  while (left < right) {
    const mid = left + Math.floor((right - left) / 2);
    if (arr[mid] < target) left = mid + 1;
    else                   right = mid;
  }
  return left; // left === right at this point
}

const sorted = [1, 3, 3, 5, 7, 9];
console.log(binarySearch(sorted, 5));  // 3
console.log(binarySearch(sorted, 4));  // -1
console.log(lowerBound(sorted, 3));    // 1 (first 3)

Why It Matters for Engineers

Binary search is the go-to algorithm for any "find in sorted" problem, and the O(log n) intuition — halving the search space each step — generalizes to many other algorithms and system designs. Database index lookups are binary searches on B-trees. Compression algorithms use binary search to find encoding lengths. Distributed systems use binary search to find split points in sorted data. The "binary search on the answer" technique — setting up a monotonic predicate and binary searching for the boundary — is one of the most powerful problem-solving patterns in competitive programming and technical interviews. Recognizing when a problem is solvable with this technique is a high-value skill.