3.1 Binary Search (1D, 2D & Answer Space)

1. What Is Binary Search?

Binary Search is a divide-and-conquer search algorithm that finds a target inside a sorted (or monotonic) collection by repeatedly checking the middle element (mid) and throwing away the entire half where the target cannot possibly be.

2. Why Do We Need Binary Search & How Does It Work?

The Pain of Linear Search (O(N)) vs. Halving (O(log N))

Suppose you have a sorted array of 1,000,000,000 (1 billion) items:

• Linear Search (for loop): Checks items one by one from index 0. Worst case: 1,000,000,000 steps.
• Binary Search: Checks the middle (500,000,000). With one comparison (< or >), it eliminates 500 million items! After 30 halvings (2^30 > 10^9), only 1 item is left. Worst case: 30 steps (O(log N))!

The 3 Core Binary Search Scenarios

1. Standard & Boundary Search: Finding an exact number (while left <= right) or finding the first index where nums[i] >= target (while left < right).

2. Rotated Sorted Arrays: When [0, 1, 2, 4, 5, 6, 7] is rotated into [4, 5, 6, 7, 0, 1, 2], at least one half ([left..mid] or [mid..right]) is still strictly sorted. Check which half is sorted, test if target lies inside that half's endpoints, and narrow the range!

3. Binary Search on Answer Space (Koko Eating Bananas): Even when there is no sorted array given, if a question asks "What is the minimum speed/capacity X needed to finish a task?", notice that can_finish(X) is monotonic: if speed X is too slow (False), every slower speed is also False; once speed X works (True), every faster speed also works (True)!

Step Through the Visual Drawing: Halving the Search Space

Click Next below to trace how Binary Search locates 23 by discarding half the array on every comparison:

3. Basic Operations & Walkthroughs (All 4 Languages)

# 1. Standard Exact Match Binary Search -> O(log N)
def binary_search(nums: list[int], target: int) -> int:
  left, right = 0, len(nums) - 1
  while left <= right:
      mid = left + (right - left) // 2
      if nums[mid] == target:
          return mid
      elif nums[mid] < target:
          left = mid + 1
      else:
          right = mid - 1
  return -1

# 2. First True / Lower Bound Template -> O(log N)
def first_feasible(min_ans: int, max_ans: int, can_finish) -> int:
  left, right = min_ans, max_ans
  while left < right:
      mid = left + (right - left) // 2
      if can_finish(mid):
          right = mid      # mid works! Keep it and try smaller
      else:
          left = mid + 1   # mid failed! Must go higher
  return left

4. Core Interview Patterns & Common Traps

left, right = min_possible, max_possible
while left < right:
  mid = left + (right - left) // 2
  if can_finish(mid):
      right = mid      # mid works! Keep mid and try smaller
  else:
      left = mid + 1   # mid is too small! Must go higher
return left

5. Practice On Your Own (Curated Submodule Problems)