# Binary Search Interview Patterns: A Complete Guide (2025)

Source: https://www.techinterview.org/post/3233460596/binary-search-interview-patterns/
Updated: 2026-07-05 · techinterview.org

## Why Binary Search Is Tested So Frequently

Binary search appears in roughly 10-15% of FAANG coding interviews, both as a standalone problem and as a subroutine inside harder problems. The core algorithm is simple — O(log n) search in a sorted array — but interview problems disguise it as: finding a boundary condition, searching in a rotated array, or applying binary search to an answer space rather than an array. Mastering the three main templates removes 95% of the difficulty.

## Template 1: Standard Binary Search


```
def binary_search(nums: list, target: int) -> int:
    left, right = 0, len(nums) - 1
    while left <= right:          # <= because single element is valid
        mid = left + (right - left) // 2   # avoids integer overflow
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1  # not found

# Time: O(log n), Space: O(1)
```


The overflow-safe mid calculation: left + (right - left) // 2 is equivalent to (left + right) // 2 but prevents integer overflow when left and right are large. In Python this is academic (arbitrary precision ints), but critical in Java and C++ where int overflow is a real bug.

## Template 2: Find Left / Right Boundary

Many problems ask for the first or last occurrence of a value, or the leftmost position where a condition becomes true. Use this template instead of Template 1.


```
# Find leftmost (first) occurrence of target
def find_left(nums: list, target: int) -> int:
    left, right = 0, len(nums)  # right is len, not len-1
    while left < right:          # strictly less than
        mid = left + (right - left) // 2
        if nums[mid] < target:
            left = mid + 1
        else:
            right = mid   # do not exclude mid yet
    return left if left < len(nums) and nums[left] == target else -1

# Find rightmost (last) occurrence of target
def find_right(nums: list, target: int) -> int:
    left, right = 0, len(nums)
    while left < right:
        mid = left + (right - left) // 2
        if nums[mid] <= target:   # note: <= instead of <
            left = mid + 1
        else:
            right = mid
    pos = left - 1
    return pos if pos >= 0 and nums[pos] == target else -1

# Count occurrences of target in sorted array
def count(nums, target):
    return find_right(nums, target) - find_left(nums, target) + 1
```


## Template 3: Binary Search on Answer

Some problems have no explicit sorted array but have a monotonic property: there is a threshold value X such that all values below X fail the condition and all values above pass (or vice versa). Binary search finds X in O(log(range)) time.


```
# Koko eating bananas: find minimum eating speed to finish all piles in H hours
def min_eating_speed(piles: list, H: int) -> int:
    def can_finish(speed: int) -> bool:
        hours = sum(-(-p // speed) for p in piles)  # ceiling division
        return hours <= H

    left, right = 1, max(piles)
    while left < right:
        mid = left + (right - left) // 2
        if can_finish(mid):
            right = mid    # try slower speed
        else:
            left = mid + 1 # need faster speed
    return left

# Minimum days to make M bouquets — same pattern
# Minimum capacity to ship packages in D days — same pattern
# Pattern: binary search on the answer value, use feasibility check function
```


## Classic Problem: Search in Rotated Sorted Array


```
# Array [4,5,6,7,0,1,2] is a rotated version of [0,1,2,4,5,6,7]
def search_rotated(nums: list, target: int) -> int:
    left, right = 0, len(nums) - 1
    while left <= right:
        mid = left + (right - left) // 2
        if nums[mid] == target:
            return mid
        # Determine which half is sorted
        if nums[left] <= nums[mid]:  # left half is sorted
            if nums[left] <= target < nums[mid]:
                right = mid - 1    # target in sorted left half
            else:
                left = mid + 1
        else:  # right half is sorted
            if nums[mid] < target <= nums[right]:
                left = mid + 1     # target in sorted right half
            else:
                right = mid - 1
    return -1
```


## Search in 2D Matrix


```
# Matrix where each row is sorted and first element of each row > last of prev row
# Treat as flattened 1D sorted array
def search_matrix(matrix: list, target: int) -> bool:
    m, n = len(matrix), len(matrix[0])
    left, right = 0, m * n - 1
    while left <= right:
        mid = left + (right - left) // 2
        val = matrix[mid // n][mid % n]  # convert 1D index to 2D
        if val == target: return True
        elif val < target: left = mid + 1
        else: right = mid - 1
    return False


# Matrix sorted left-to-right per row and top-to-bottom per column
# Staircase search from the top-right corner
def search_matrix_ii(matrix: list, target: int) -> bool:
    row, col = 0, len(matrix[0]) - 1
    while row < len(matrix) and col >= 0:
        if matrix[row][col] == target: return True
        elif matrix[row][col] > target: col -= 1   # too big, go left
        else: row += 1                              # too small, go down
    return False
```


## Common Binary Search Interview Problems

- Template 1: Binary Search, Guess Number Higher or Lower, First Bad Version

- Template 2: Find First and Last Position, Find Minimum in Rotated Array, Peak Index in Mountain Array

- Template 3: Koko Eating Bananas, Capacity to Ship Packages, Minimum Days to Make Bouquets, [Median of Two Sorted Arrays](https://www.techinterview.org/post/3233474762/median-of-two-sorted-arrays-binary-search/)

- Rotated array: Search in Rotated Sorted Array (I and II with duplicates)

- 2D: Search a 2D Matrix (I and II), Kth Smallest in Sorted Matrix

## Interview Approach

- Identify monotonicity: if the problem has a sorted array OR a condition that flips from false to true at some threshold, binary search applies

- Choose the right template before writing code — boundary template bugs are the most common interview mistake

- Loop invariant: know what left and right mean at every iteration

- Always check: what does the loop return when target is not found?

- Off-by-one: use left less than right (Template 2/3) or left less than or equal to right (Template 1) consistently

## Frequently Asked Questions

### What are the three binary search templates and when do you use each?

Template 1 (standard): find a specific target value in a sorted array. Loop condition: left <= right. Returns the index of target or -1. Use for: basic search, fixed target value. Template 2 (boundary): find the leftmost or rightmost position where a condition is true. Loop condition: left < right (strictly less than). Right initializes to len(nums), not len(nums)-1. The loop exits with left == right pointing to the answer. Use for: first/last occurrence, minimum in rotated array, peak finding. Template 3 (answer space): binary search on the answer value rather than an array index. Define a feasibility function that returns true or false. Binary search finds the minimum (or maximum) value for which feasibility is true. Use for: Koko eating bananas, capacity to ship packages, minimum days to make bouquets. Recognizing which template applies is the key skill.

### How do you search in a rotated sorted array?

A rotated sorted array like [4,5,6,7,0,1,2] still has the property that at least one half (from mid to left or mid to right) is always sorted. The algorithm: check if the left half (nums[left] to nums[mid]) is sorted. If nums[left] <= nums[mid], the left half is sorted. Then check if the target falls within the sorted left half — if yes, search left; otherwise search right. If the left half is not sorted, the right half must be sorted. Check if target falls within the sorted right half — if yes, search right; otherwise search left. This produces an O(log n) solution without needing to find the rotation point first. For the follow-up with duplicates (nums[left] == nums[mid] is ambiguous), increment left by one to shrink the ambiguous case, making worst case O(n).

### What is binary search on the answer and how do you recognize it?

Binary search on the answer applies when: (1) the answer is a value within a known range (not an index in an array), (2) there is a monotonic feasibility function — values below the threshold are infeasible and above are feasible (or vice versa), and (3) a brute force search over all possible answers would be too slow. The pattern: set left = minimum possible answer, right = maximum possible answer, write a can_achieve(mid) function that tests whether answer mid is feasible, then binary search to find the minimum feasible value. Examples: find minimum eating speed so all piles are eaten in H hours (feasibility: total hours at this speed <= H); find minimum ship capacity to deliver all packages in D days (feasibility: packages fit in D days at this capacity). The feasibility function often runs in O(n), making the total complexity O(n log(range)).

- [Snap Interview Guide](https://techinterview.org/snap-software-engineer-interview/)

- [DoorDash Interview Guide](https://techinterview.org/doordash-interview-guide/)

- [Coinbase Interview Guide](https://techinterview.org/coinbase-interview-guide/)

- [Atlassian Interview Guide](https://techinterview.org/atlassian-interview-guide/)

- [LinkedIn Interview Guide](https://techinterview.org/linkedin-interview-guide/)

- [Uber Interview Guide](https://techinterview.org/uber-interview-guide/)

- [Apple Interview Guide](https://techinterview.org/apple-interview-guide/)

## Companies That Ask This

- [Meta Interview Guide](https://techinterview.org/meta-interview-guide/)

🏢 Asked at: [Databricks Interview Guide 2026: Spark Internals, Delta Lake, and Lakehouse Architecture](https://techinterview.org/databricks-interview-guide/)