Binary Search Interview Patterns

When should you use binary search in a coding interview?

Use binary search whenever the problem involves a sorted array or a search space where you can eliminate half the possibilities at each step. Key signals include the problem asking for a target in a sorted array, finding a boundary condition, or optimizing over a monotonic function. Binary search runs in O(log n) and is often the key to transforming a brute force O(n) solution into an optimal one.

---

Binary search is one of the most elegant and frequently misapplied algorithms in coding interviews. Most candidates know the basic form — find a target in a sorted array — but miss the dozens of problem variants where binary search is the key insight. Understanding the general principle of binary search (repeatedly eliminating half the search space based on a condition) rather than just the template is what enables you to recognize and apply it across the full range of interview problems.

The Core Principle of Binary Search

Binary search works on any problem where:

1. The search space can be ordered
2. At each step, you can determine which half of the remaining space to eliminate

This is broader than "find X in a sorted array." The search space might be a range of possible answers (not an array), and the condition that eliminates half the space might be a computed function, not a direct comparison.

"Most candidates who struggle with binary search on medium and hard problems understand the algorithm but have internalized too narrow a definition of when to apply it. Binary search is not just for sorted arrays — it is for any monotonic condition over an ordered space." — Software Engineer, interview preparation coach

The Binary Search Template

The most common source of bugs in binary search implementations is the loop condition and the index update logic. This template handles the most common cases correctly.

def binary_search(array, target):
    left, right = 0, len(array) - 1
    
    while left <= right:
        mid = left + (right - left) // 2  # Avoids integer overflow
        
        if array[mid] == target:
            return mid
        elif array[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    
    return -1  # Not found

Template Variants: Finding Boundaries

Many binary search problems ask you to find the leftmost or rightmost occurrence of a value, or a boundary position.

Finding the left boundary (first occurrence):

def left_boundary(array, target):
    left, right = 0, len(array)
    
    while left < right:
        mid = left + (right - left) // 2
        if array[mid] < target:
            left = mid + 1
        else:
            right = mid
    
    return left  # Returns index of first occurrence, or insertion point

Finding the right boundary (last occurrence):

def right_boundary(array, target):
    left, right = 0, len(array)
    
    while left < right:
        mid = left + (right - left) // 2
        if array[mid] <= target:
            left = mid + 1
        else:
            right = mid
    
    return left - 1  # Returns index of last occurrence

Common Binary Search Problem Categories

Category 1: Classic Search in Sorted Array

Find a target value or determine it is absent. The foundational form.

Example problems:

• Binary Search (LeetCode 704)
• Search in a 2D Matrix
• Search Insert Position

Category 2: Search in Modified Sorted Array

The array has been rotated, has duplicates, or has other modifications that require careful handling.

Example problems:

• Search in Rotated Sorted Array: If array[mid] >= array[left], the left half is sorted. Check if target is in the sorted half; if not, search the other half.
• Find Minimum in Rotated Sorted Array: The minimum is at the rotation point.
• Find Peak Element: Binary search on slope direction.

Category 3: Finding a Boundary (Not an Exact Value)

Find the first/last index satisfying a condition.

Example problems:

• First Bad Version: Find the first "true" in a boolean array
• Sqrt(x): Find the last integer whose square is <= x
• Capacity to Ship Packages Within D Days (binary search on the answer)

Template for boundary search:

def find_boundary(condition_func, left, right):
    while left < right:
        mid = left + (right - left) // 2
        if condition_func(mid):
            right = mid
        else:
            left = mid + 1
    return left

Category 4: Binary Search on the Answer

This is the most advanced and commonly missed pattern. Instead of searching an array, you search over a range of possible answers to an optimization problem.

Key insight: The answer to an optimization problem often has a monotonic property — if a capacity C is sufficient, then all capacities > C are also sufficient. This means you can binary search on the answer.

Problem: Koko Eating Bananas — Given piles of bananas and H hours, find the minimum eating speed k such that Koko can eat all bananas in H hours.

• Binary search on k from 1 to max(piles)
• For each candidate k, check if k is feasible (can eat all piles in H hours)
• Find the minimum feasible k

Problem: Minimum Number of Days to Make m Bouquets

• Binary search on the number of days
• For each candidate day count, check if m bouquets can be made

Binary Search Category	Search Space	Condition
Classic search	Array indices	array[mid] == target
Rotated array	Array indices	Which half is sorted
Boundary search	Array indices	First/last satisfying condition
Answer search	Value range	Is this answer feasible?

Step-by-Step Approach to Binary Search Problems

Step 1: Identify the Search Space

What are the boundaries of what you are searching? For an array, it is the index range. For answer search, it might be 1 to max(array) or 0 to 10^9.

Step 2: Define the Condition

What condition determines whether to search left or right? For classic search, it is a comparison. For answer search, it is a feasibility check.

Step 3: Choose the Template

• Exact value: use the left <= right template with three branches
• Boundary (leftmost): use left < right with right = mid when condition is true
• Boundary (rightmost): use left < right with left = mid + 1 when condition is true

Step 4: Check the Loop Invariant

At the end of the binary search, what does left or right represent? Verify that your exit condition returns the correct value.

Common Binary Search Bugs and Fixes

Bug	Example	Fix
Integer overflow	mid = (left + right) / 2	Use mid = left + (right - left) // 2
Infinite loop	right = mid without left < right	Use left < right when right = mid
Off-by-one in boundary search	Return left instead of left - 1 for right boundary	Trace through a small example to verify
Wrong initial range for answer search	Starting range too small	Set right to max possible valid answer
Missing feasibility edge cases	Checking feasibility incorrectly	Test feasibility function independently

---

Frequently Asked Questions

How do I decide between left <= right and left < right as the loop condition? Use left <= right for exact value searches where you will explicitly return when found. Use left < right for boundary searches where you want left and right to converge to the same point. The key rule: with left < right, right = mid is safe because if left < right, then mid < right and you make progress. With left <= right, use left = mid + 1 and right = mid - 1 to ensure progress.

How do I recognize a "binary search on the answer" problem? Look for optimization problems where you are asked for the minimum or maximum of some value, and where feasibility is monotonic — if value X is feasible, all values larger than X (for minimization) are also feasible. Also look for problems with a large value range as an answer space (days, speeds, capacities) combined with a O(n) feasibility check that would give O(n log n) total complexity.

What is the time complexity of binary search on a sorted matrix? For an m x n matrix where each row and column is sorted independently (not the entire matrix sorted as a flattened array), binary search alone is not sufficient. You need a different technique (search from top-right corner). For a matrix where all rows are sorted and the last element of each row is smaller than the first element of the next, you can treat it as a 1D sorted array and apply standard binary search in O(log(mn)).

References

1. Sedgewick, R., & Wayne, K. (2011). Algorithms (4th ed., Chapter 3.1: Symbol Tables). Addison-Wesley Professional.
2. Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed.). MIT Press.
3. Knuth, D. E. (1998). The Art of Computer Programming, Vol. 3: Sorting and Searching (2nd ed.). Addison-Wesley.
4. Gayle Laakmann McDowell. (2015). Cracking the Coding Interview (6th ed.). CareerCup.
5. LeetCode Editorial Team. (2023). Binary search patterns and templates. LeetCode Explore.