Binary Search: Complete Guide with Advanced Variations

Binary search turns a linear scan into a logarithmic one. Instead of checking every element, which costs

Definition: given a sorted array and a target, maintain a search window with left and right pointers. At each step, check the middle element. If it matches, you are done. If the target is smaller, discard the right half. If it is larger, discard the left half. Repeat until the window is empty.

Real-World Analogy

Imagine you are looking for a word in a physical dictionary. Opening to a random page and scanning each word one by one takes forever. Instead, you open the book in the middle. If the words on that page start with M, and you are looking for Pattern, you know the word must be in the right half. You just eliminated half the dictionary in one step. You open the middle of the right half and repeat. In a 1000-page book, you find any word in about 10 steps.

Visual Explanation

Binary search works by maintaining a search window defined by two pointers that close in on the target.

    graph TD
    A["Initialize left=0, right=n-1"] --> B{"left <= right?"}
    B -->|Yes| C["Calculate mid = left + (right - left) / 2"]
    C --> D{"nums[mid] == target?"}
    D -->|Yes| E["Return mid"]
    D -->|No| F{"nums[mid] < target?"}
    F -->|Yes| G["left = mid + 1"]
    F -->|No| H["right = mid - 1"]
    G --> B
    H --> B
    B -->|No| I["Return -1"]
  

Three things happen on every iteration. First, calculate the midpoint using left + (right - left) / 2 to avoid integer overflow. Second, compare the value at that index to the target. Third, if there is no match, shrink the window by moving one pointer past the midpoint. The loop stops when left passes right, meaning the target is not in the array.

When to Use This Pattern

These characteristics tell you binary search is the right tool.

• The input is sorted (or can be sorted without losing information). Binary search relies on the ability to discard one half of the search space based on a comparison, which only works if the data has a defined order.
• You need to find a specific element, a boundary (first or last occurrence), or an insertion point. All of these are variations of the same narrowing loop.
• The problem asks for the minimum or maximum value that satisfies a condition, often called binary search on answer. You search the space of possible answers instead of the array itself.
• You need better than
  O(N)
  time and the data supports it. If the constraints give you massive input sizes, logarithmic time is probably expected.

Complexity Analysis

The time complexity comes from repeatedly dividing N by 2 until 1 element remains. If N is 16, you need at most 4 comparisons. If N is 1,048,576, you need at most 20. That scaling is what makes binary search the default choice for sorted-data lookups. The space cost is constant because the recursive version is rarely used in practice; the iterative version uses three integer variables.

Common Mistakes

Integer overflow with midpoint calculation. Writing mid = (left + right) / 2 works in Python but can overflow in Java, C++, and other languages when left + right exceeds the maximum integer value. Use left + (right - left) / 2 instead. The subtraction is safe because right - left is always less than or equal to the input size.

To catch this during practice, check what happens when left is near Integer.MAX_VALUE / 2 and right is near Integer.MAX_VALUE. The sum overflows but the subtraction does not.

Off-by-one in the loop condition. Using while (left < right) when the intent is while (left <= right) causes the loop to exit before checking the last element. With left < right, when left == right the loop terminates, even though that single remaining element has not been compared to the target. The fix is to decide on a consistent convention and stick with it. The standard template uses <= for exact-match search and < for lower-bound search.

Setting left = mid instead of left = mid + 1. When mid is not the target and you know the target cannot exist at mid, you should exclude it from the new search window. Using left = mid instead of left = mid + 1 creates an infinite loop when left and right become adjacent, because mid floors to left and the window never shrinks.

Forgetting that binary search on answer requires a monotonic predicate. Binary search on answer only works if there is a clear yes/no threshold. For example, “can this speed Koko finish all bananas in H hours?” is yes for large K and no for small K, with a single transition point. If the predicate is not monotonic, binary search gives a wrong answer.

Related Patterns

• Two Pointers . Two pointers also uses left and right indices, but the pointers move based on element values rather than halving the search space. Two pointers handles unsorted arrays and pair-finding; binary search requires sorted data.
• Divide and Conquer . Binary search is the simplest divide-and-conquer algorithm. The full pattern covers recursive splitting for problems like merge sort and the Master Theorem.
• Binary Search Tree . BSTs apply the same logarithmic search idea to a tree structure, where the decision to go left or right replaces the midpoint calculation.

Next Steps

Once the concept is clear, the next step is making the code automatic. Check out the code templates for memorizable implementations in 6 languages, then work through the practice problems to apply the pattern to real interview questions.