Coding Patterns
Binary Search

Binary Search

The Binary Search algorithm is a classic “divide and conquer” technique that turns a slow

O(N)
linear scan into a lightning-fast
O(log N)
search. It is one of the most frequently tested patterns in technical interviews.

Real-World Analogy

Imagine you are looking for a word in a physical dictionary.

  • The Brute Force Way: You start from the first page and check every single word until you find “Pattern”. This takes forever.
  • The Binary Search Way: You open the book in the middle.
    • If the current words start with ‘M’, you know “Pattern” must be in the right half. You’ve just eliminated half the book!
    • You open the middle of the remaining right half.
    • Repeat this until you find your word.

By repeatedly cutting the search space in half, you find any word in a 1000-page book in about 10 steps.

Visual Explanation

Binary search works by maintaining a “search window” defined by two pointers: left and right.

  graph TD
    subgraph Iteration1 ["1. Initial Range"]
        A1[1] --- A2[3] --- A3[5] --- A4[7] --- A5[9] --- A6[11] --- A7[13]
        L1[left] -.-> A1
        R1[right] -.-> A7
        M1[mid] -.-> A4
    end

    subgraph Iteration2 ["2. Target > Mid: Shrink Left"]
        B1[x] --- B2[x] --- B3[x] --- B4[x] --- B5[9] --- B6[11] --- B7[13]
        L2[left] -.-> B5
        R2[right] -.-> B7
        M2[mid] -.-> B6
    end

    subgraph Iteration3 ["3. Target < Mid: Shrink Right"]
        C1[x] --- C2[x] --- C3[x] --- C4[x] --- C5[9] --- C6[x] --- C7[x]
        L3[left] -.-> C5
        R3[right] -.-> C5
        M3[mid] -.-> C5
    end

Steps:

  1. Calculate Mid: Find the middle index of the current range.
  2. Compare: Check if nums[mid] is your target.
  3. Halve: If not found, move either the left or right pointer to eliminate the half where the target cannot possibly exist.

When to Use This Pattern

Use the Binary Search pattern when the following conditions are met:

  • The input data is sorted (or can be sorted).
  • You need to find a specific element, boundary, or insertion point.
  • You need better than
    O(N)
    time complexity.
  • The problem asks for the “minimum” or “maximum” value that satisfies a condition (Binary Search on Answer).

Complexity Analysis

MetricComplexityExplanation
Time
O(log N)
Each step reduces the search space by half. For $N$ elements, it takes $\log_2 N$ steps to reach a single element.
Space
O(1)
Iterative binary search only uses a few pointers (left, right, mid), regardless of input size.

Common Mistakes

  1. Integer Overflow: Calculating mid = (left + right) / 2 can overflow in some languages if left and right are large. Use left + (right - left) / 2 instead.
  2. Off-by-One in Boundaries: Using while (left < right) when you should use while (left <= right) (or vice versa) often leads to missing the target or infinite loops.
  3. Updating Pointers: Forgetting to move the pointer past the middle element (e.g., left = mid instead of left = mid + 1) can trap the algorithm in an infinite loop when left and right are adjacent.

Next Steps

Now that you understand the theory, check out the implementation templates and practice problems: