Binary Search

Binary Search

Eliminate half the search space every step. O(log n) — at n=1,000,000, only 20 steps needed.

Binary Search — Step by Step
LEFT RIGHT MID FOUND
Press Start to begin. Array is sorted.

Why It's O(log n)

Each Step Halves the Problem
Start with n elements. After 1 step: n/2. After 2: n/4. After k steps: n/2ᵏ. When n/2ᵏ = 1, we're done. So k = log₂(n) steps.
nMax Steps
164
1,00010
1,000,00020
1,000,000,00030
Critical Rule
Use left <= right for classic search (single-element arrays must be checked). Use left < right for answer-space binary search.

Binary Search on Answer Space

The Key Insight
Instead of searching for a value in an array, you binary search the range of possible answers. Ask: "Is mid a feasible answer?" Eliminate half the answer space each time.
Trigger Phrases
  • "Find minimum X such that condition holds"
  • "Find maximum X such that condition holds"
  • "Minimum speed / capacity / days to complete task"
Koko Eating Bananas — Answer Space Search

Piles: [3, 6, 7, 11]. Hours limit h=8. Find minimum eating speed k.

Answer space (possible speeds 1 to 11):
Press Animate to see binary search on answer space.

Template 1 — Classic (Find Exact Value)

def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:   # <= checks single element
        mid = left + (right - left) // 2  # avoids overflow
        if   arr[mid] == target: return mid
        elif arr[mid] <  target: left  = mid + 1
        else:                    right = mid - 1
    return -1  # not found

# Search Insert Position — return left at end
def search_insert(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if   arr[mid] == target: return mid
        elif arr[mid] <  target: left  = mid + 1
        else:                    right = mid - 1
    return left  # insert position

Template 2 — Answer Space Search

def min_feasible_answer(arr, limit):
    def feasible(mid):
        # return True if mid satisfies the condition
        return sum(-(-x // mid) for x in arr) <= limit

    left, right = 1, max(arr)
    while left < right:          # < not <= for answer search
        mid = (left + right) // 2
        if feasible(mid):
            right = mid            # mid works, try smaller
        else:
            left = mid + 1        # mid doesn't work, need bigger
    return left
Key Difference
Classic search: left <= right. Answer-space: left < right. When feasible(mid) is True, right = mid (not mid-1) to preserve the answer.

LeetCode Problems

  • EasyBinary SearchClassic template
  • EasySearch Insert PositionReturn left at end
  • MediumFind Minimum in Rotated Sorted ArrayModified binary search
  • MediumSearch in Rotated Sorted ArrayWhich half is sorted?
  • MediumKoko Eating BananasAnswer space search
  • MediumCapacity to Ship PackagesAnswer space search
  • HardMedian of Two Sorted ArraysBinary search on partition