Binary Search: The Complete Interview Guide

Why Binary Search Matters

Binary search is one of the most fundamental algorithms in computer science. It reduces O(n) linear search to O(log n) by repeatedly dividing the search space in half. If you can search 1 million elements in 20 comparisons instead of 1 million, that's the power of logarithmic time.

In interviews, binary search appears constantly—not just for "find element in sorted array" but for problems like finding the minimum in a rotated array, searching in a matrix, or finding the first/last occurrence of a value.

The Universal Template

Most binary search bugs come from getting the boundary conditions wrong. Here's a template that eliminates those errors:

function binarySearch(arr: number[], target: number): number {
  let left = 0
  let right = arr.length - 1

  while (left <= right) {
    const mid = Math.floor(left + (right - left) / 2)

    if (arr[mid] === target) {
      return mid
    } else if (arr[mid] < target) {
      left = mid + 1
    } else {
      right = mid - 1
    }
  }

  return -1 // not found
}

Key Details

• left + (right - left) / 2 instead of (left + right) / 2 prevents integer overflow
• left <= right ensures we check all elements including when left === right
• mid + 1 and mid - 1 prevent infinite loops by always shrinking the search space

Variation 1: Find Lower Bound

Find the first position where you could insert the target while maintaining sorted order. This is the leftmost index where arr[index] >= target.

function lowerBound(arr: number[], target: number): number {
  let left = 0
  let right = arr.length

  while (left < right) {
    const mid = Math.floor(left + (right - left) / 2)

    if (arr[mid] < target) {
      left = mid + 1
    } else {
      right = mid
    }
  }

  return left
}

Notice the differences: right starts at arr.length (not length - 1), we use left < right (not <=), and we set right = mid (not mid - 1). This finds the insertion point.

Variation 2: Find Upper Bound

Find the first position where arr[index] > target. Useful for finding the range of elements equal to target.

function upperBound(arr: number[], target: number): number {
  let left = 0
  let right = arr.length

  while (left < right) {
    const mid = Math.floor(left + (right - left) / 2)

    if (arr[mid] <= target) {  // Note: <= instead of <
      left = mid + 1
    } else {
      right = mid
    }
  }

  return left
}

Variation 3: First and Last Occurrence

A common interview question: find the first and last position of a target in a sorted array with duplicates.

function searchRange(nums: number[], target: number): number[] {
  const first = findFirst(nums, target)
  if (first === -1) return [-1, -1]
  const last = findLast(nums, target)
  return [first, last]
}

function findFirst(nums: number[], target: number): number {
  let left = 0, right = nums.length - 1
  let result = -1

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

function findLast(nums: number[], target: number): number {
  let left = 0, right = nums.length - 1
  let result = -1

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

Variation 4: Search in Rotated Sorted Array

Classic interview problem: the array was sorted but then rotated at some pivot. Find the target.

function searchRotated(nums: number[], target: number): number {
  let left = 0, right = nums.length - 1

  while (left <= right) {
    const mid = Math.floor(left + (right - left) / 2)

    if (nums[mid] === target) return mid

    // Determine which half is sorted
    if (nums[left] <= nums[mid]) {
      // Left half is sorted
      if (target >= nums[left] && target < nums[mid]) {
        right = mid - 1
      } else {
        left = mid + 1
      }
    } else {
      // Right half is sorted
      if (target > nums[mid] && target <= nums[right]) {
        left = mid + 1
      } else {
        right = mid - 1
      }
    }
  }

  return -1
}

Binary Search on Answer

A powerful technique: instead of searching an array, search the space of possible answers. If you can phrase a problem as "find the minimum/maximum value X such that condition(X) is true", you can often binary search.

Examples:

• Koko Eating Bananas - Find minimum eating speed to finish in H hours
• Capacity to Ship Packages - Find minimum ship capacity to ship in D days
• Split Array Largest Sum - Minimize the maximum sum when splitting array

// Template for "binary search on answer"
function binarySearchAnswer(
  minVal: number,
  maxVal: number,
  isValid: (x: number) => boolean
): number {
  let left = minVal
  let right = maxVal

  while (left < right) {
    const mid = Math.floor(left + (right - left) / 2)

    if (isValid(mid)) {
      right = mid  // mid works, try smaller
    } else {
      left = mid + 1  // mid doesn't work, need larger
    }
  }

  return left
}

Common Mistakes to Avoid

1. Integer overflow - Always use left + (right - left) / 2
2. Infinite loops - Make sure left and right always move toward each other
3. Off-by-one on boundaries - Carefully consider whether right should be length or length - 1
4. Wrong comparison operator - < vs <= in the while condition matters
5. Not handling empty array - Check edge cases before the loop

Time and Space Complexity

• Time: O(log n) - we halve the search space each iteration
• Space: O(1) - only using a few variables

Practice Problems

Try these problems to solidify your understanding:

1. Easy: Binary Search (LeetCode 704)
2. Easy: Search Insert Position (LeetCode 35)
3. Medium: Find First and Last Position (LeetCode 34)
4. Medium: Search in Rotated Sorted Array (LeetCode 33)
5. Medium: Find Minimum in Rotated Sorted Array (LeetCode 153)
6. Medium: Koko Eating Bananas (LeetCode 875)
7. Hard: Median of Two Sorted Arrays (LeetCode 4)

Key Takeaways

• Binary search reduces O(n) to O(log n) by halving the search space
• Use the template and understand why each detail matters
• Lower/upper bound variations are essential for range queries
• "Binary search on answer" applies to optimization problems
• Practice until the boundary conditions become second nature