Binary Search: The Complete Guide

Binary search is one of the most common interview topics. It's simple in theory, but has surprising depth. This guide takes you from the basics to advanced variants.

Why Binary Search?

Binary search works on sorted arrays and runs in O(log n) time. Compared to linear search at O(n), it scales massively:

| Array size | Linear search | Binary search | |-----------|---------------|---------------| | 1,000 | ~1,000 ops | ~10 ops | | 1,000,000 | ~1,000,000 ops | ~20 ops | | 1,000,000,000 | ~1B ops | ~30 ops |

The Core Template

typescriptCopy
function binarySearch(nums: number[], target: number): number {
  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
}

Why left + (right - left) / 2?

The naive mid = (left + right) / 2 can overflow in languages with fixed-width integers (C, Java, older C++). The safer form avoids it. In JS/TS it doesn't matter, but it's a good habit.

Variant 1: Find Leftmost / Rightmost

When duplicates exist, the basic template only finds an occurrence. To find the leftmost or rightmost:

typescriptCopy
// Leftmost: first index where nums[i] >= target
function lowerBound(nums: number[], target: number): number {
  let left = 0, right = nums.length
  while (left < right) {
    const mid = left + Math.floor((right - left) / 2)
    if (nums[mid] < target) left = mid + 1
    else right = mid
  }
  return left
}

// Rightmost: last index where nums[i] <= target
function upperBound(nums: number[], target: number): number {
  let left = 0, right = nums.length
  while (left < right) {
    const mid = left + Math.floor((right - left) / 2)
    if (nums[mid] <= target) left = mid + 1
    else right = mid
  }
  return left - 1
}

Variant 2: Search on Answer

Some problems don't search an array — they search a range of possible answers.

Given n workers producing units[i] items/day, find the minimum number of days to produce at least m items.

typescriptCopy
function minDays(units: number[], m: number): number {
  let left = 1
  let right = Math.max(...units) * m  // worst case

  while (left < right) {
    const mid = left + Math.floor((right - left) / 2)
    const total = units.reduce((sum, u) => sum + Math.floor(mid / u) * u, 0)

    if (total >= m) right = mid
    else left = mid + 1
  }

  return left
}

The trick: the answer space is monotonic — if we can do it in k days, we can do it in any k' >= k days.

Common Pitfalls

1. Infinite loop: when left == right but you keep looping. Always ensure the loop terminates.
2. Off-by-one: left <= right vs left < right. Pick one and be consistent.
3. Empty array: handle nums.length === 0 first.
4. Integer overflow: use left + (right - left) / 2.
5. Mid computation order: Math.floor((left + right) / 2) can have precision issues in some languages.

Practice Problems

Here are 5 problems in increasing difficulty:

| # | Problem | Variant | |---|---------|---------| | 1 | LeetCode 704: Binary Search | Basic | | 2 | LeetCode 34: Find First and Last Position | Lower/Upper bound | | 3 | LeetCode 33: Search in Rotated Sorted Array | Modified array | | 4 | LeetCode 1539: Kth Missing Positive | Search on answer | | 5 | LeetCode 4: Median of Two Sorted Arrays | Advanced |

Mental Model

When you see a problem, ask yourself:

1. Is the data sorted? → Binary search candidate.
2. Is the answer space monotonic? → Binary search on answer.
3. What are the boundaries? → Define left and right precisely before coding.

Binary search isn't just about arrays. It's a way of thinking: repeatedly halve the problem space until you converge on the answer.

Master this template and you'll recognize binary search problems in any disguise.