Binary Search

The Algorithm

Binary search works by repeatedly dividing the search interval in half. If the value of the search key is less than the item in the middle of the interval, narrow the interval to the lower half. Otherwise, narrow it to the upper half. You continue this until the value is found or the interval is empty.

A Robust Implementation:

Implementing binary search correctly can be tricky, with off-by-one errors being common. Here's a robust template:

# Python: Find first element >= x
def binary_search(arr, x):
  left, right = 0, len(arr)
  ans = -1 # Or some other indicator for 'not found'
  while left < right:
    mid = left + (right - left) // 2
    if arr[mid] >= x:
      ans = mid
      right = mid
    else:
      left = mid + 1
  return ans

Time Complexity: O(log n), because we discard half of the search space with each comparison.

Space Complexity: O(1) for the iterative version.

Interactive Demo

Use the simulation below to visualize how binary search narrows down the search space on a sorted array.

Binary Search on the Answer

A powerful application of binary search is not on the data itself, but on the range of possible answers to a problem. This is applicable to optimization problems where you need to find the minimum or maximum value that satisfies a certain condition.

Monotonicity: The key is that the condition must be "monotonic". This means if a value 'x' is a valid solution, then all values on one side of 'x' (e.g., all values > x, or all values < x) are also valid solutions. This creates a sorted-like structure of booleans (e.g., F F F F T T T T) where you can binary search for the first 'T' (the minimum valid answer) or the last 'T' (the maximum valid answer).

Example Problem (from CSES): You have n machines and t products to create. Machine k takes m_k seconds per product. What is the minimum time needed to produce all t products?

Solution: You can binary search on the answer (the time).
- The search space for time is from 1 to a large number (e.g., 10¹⁸).
- For a given time T, can we produce at least t products? This check is easy: for each machine, we can produce floor(T / m_k) products. We sum this over all machines.
- This check function is monotonic: if we can produce t products in time T, we can also do it in any time T' > T.
- We binary search for the minimum T for which the check is true.