10 Binary Search Interview Problems That Build Real Intuition

You have "mastered" binary search. You know it's O(log n). You've nodded confidently when someone mentions divide and conquer. Then the interviewer says "find the first bad version" and suddenly your hands are writing a linear scan and your brain is just watching.

That gap, between knowing what binary search is and actually running it correctly under pressure, is what kills candidates. Not difficulty. Not obscure tricks. Just the wrong loop condition, the off-by-one on the boundary update, or the search space that quietly excludes the answer before you even start.

These ten problems were chosen for what they teach, not just difficulty. Work through them in order and you will have seen every variation the interview circuit throws at you: standard search, boundary finding, rotated arrays, 2D matrices, answer-space search, and partition-based median finding.

The Invariant Behind Every Binary Search Interview Problem

Binary search works because of an invariant, not because of a loop structure. The invariant: the target, if it exists, is always inside the current [lo, hi] range. Every pointer update must preserve it, or you silently throw away the answer and then stare at a wrong index with no idea why.

def binary_search(nums, target):
    lo, hi = 0, len(nums) - 1
    while lo <= hi:
        mid = lo + (hi - lo) // 2
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

Use mid = lo + (hi - lo) // 2 instead of (lo + hi) // 2. Python integers don't overflow, but Java and C++ will punish the naive form on large inputs. For a full treatment of what goes wrong when the invariant breaks, see the binary search invariant guide.

1. LeetCode 704: Binary Search - Nail the Off-by-One Before You Move On

This is the template problem. That makes it the most important one to get exactly right before moving forward.

The critical decision: while lo <= hi vs while lo < hi. The <= version exits when the search space is empty. The < version exits with lo == hi, requiring different update rules. Use <= with hi = mid - 1 and lo = mid + 1. Mixing <= with hi = mid causes an infinite loop when lo == hi.

Solve it without looking anything up. Then explain out loud why the loop terminates. If you stumble explaining this on the easy problem, the later ones will expose every gap in vivid, embarrassing detail. The full bug catalog: binary search bugs.

The off-by-one you introduced at line 3 will dodge every test case you write, then show up live.

2. LeetCode 278: First Bad Version - Your Loop Is Finding a Boundary

You have n versions. Once a version is bad, all subsequent versions are bad. Find the first bad one while minimizing API calls.

The twist: you are not searching for a specific value. You are finding the leftmost position where a condition flips from false to true. When isBadVersion(mid) is true, you cannot return immediately. You set hi = mid and keep searching left.

def firstBadVersion(n):
    lo, hi = 1, n
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if isBadVersion(mid):
            hi = mid
        else:
            lo = mid + 1
    return lo

Notice: while lo < hi, exits with lo == hi. That is the boundary-search template. It reappears in every "find first occurrence," "find leftmost position," and "find minimum satisfying" variant. If you understand why hi = mid instead of hi = mid - 1, you understand the whole pattern.

3. LeetCode 35: Search Insert Position - What `lo` Means at Exit

Same setup as 704, but the target might not exist. Return the index where it would be inserted to keep the array sorted.

No special-casing needed. When binary search exits without finding the target, lo is the insertion point. The loop maintains that anything left of lo is smaller than target and anything right of hi is larger. When lo > hi, lo points exactly where target belongs.

Write the standard search loop and return lo on no match. Off-by-one bugs here almost always come from adding special cases instead of trusting the invariant. More in the off-by-one errors in binary search breakdown.

4. LeetCode 153: Find Minimum in Rotated Sorted Array - Compare Against Right

The array [4, 5, 6, 7, 0, 1, 2] was once sorted. It was rotated at some pivot. Find the minimum.

Compare nums[mid] to nums[hi], not nums[lo]. If nums[mid] > nums[hi], the rotation happened in the right half, so the minimum is there. If nums[mid] <= nums[hi], the minimum is in the left half including mid.

Comparing to lo gives you no information because lo and mid always start in the same sorted segment. This is the mistake almost everyone makes on their first attempt. You're not special. Neither was I.

def findMin(nums):
    lo, hi = 0, len(nums) - 1
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if nums[mid] > nums[hi]:
            lo = mid + 1
        else:
            hi = mid
    return nums[lo]

The boundary-search template from problem 2 reappears here: while lo < hi, exit with lo == hi, hi = mid when mid is a candidate.

5. LeetCode 33: Search in Rotated Sorted Array - Identify the Sorted Half First

Now you need to find a specific target in the rotated array. The minimum trick from problem 4 is not enough. You need to determine which half is sorted, then check whether the target falls in that half.

def search(nums, target):
    lo, hi = 0, len(nums) - 1
    while lo <= hi:
        mid = lo + (hi - lo) // 2
        if nums[mid] == target:
            return mid
        if nums[lo] <= nums[mid]:        # left half is sorted
            if nums[lo] <= target < nums[mid]:
                hi = mid - 1
            else:
                lo = mid + 1
        else:                            # right half is sorted
            if nums[mid] < target <= nums[hi]:
                lo = mid + 1
            else:
                hi = mid - 1
    return -1

The structural lesson: binary search does not require the entire array to be sorted. It requires that every step eliminates one half of the search space with certainty. This problem proves that directly. Once that clicks, a whole category of problems opens up.

6. LeetCode 74: Search a 2D Matrix - Flatten the Index

An m x n matrix where each row is sorted left to right and the first element of each row is greater than the last element of the previous row. Search for a target.

The matrix is a sorted array in disguise. Run standard binary search on indices 0 to m * n - 1. Convert mid back to 2D coordinates with row = mid // n and col = mid % n.

The lesson is not the math. The lesson is recognizing when a problem reduces to a structure you already know how to search. That reduction, seeing the sorted 1D array hiding inside the grid, separates candidates who pattern-match from candidates who actually problem-solve.

7. LeetCode 875: Koko Eating Bananas - Binary Search Without an Array

Koko has piles of bananas. She has h hours. She eats at speed k bananas per hour (rounding up per pile). Find the minimum k that lets her finish in time.

There is no sorted array of speeds to search. You construct the search space. The range is [1, max(piles)], and the key insight is that the feasibility function is monotonic: if speed k works, speed k+1 also works. Monotonic feasibility means binary search applies.

def minEatingSpeed(piles, h):
    lo, hi = 1, max(piles)
    while lo < hi:
        mid = lo + (hi - lo) // 2
        hours = sum(-(-p // mid) for p in piles)  # ceiling division
        if hours <= h:
            hi = mid
        else:
            lo = mid + 1
    return lo

This is binary search on the answer. The pattern: identify a monotonic yes/no feasibility function, find its boundary. For the full treatment of this pattern, see binary search on the answer.

Koko Eating Bananas is where you discover how much you've been leaning on autocomplete for the ceiling division syntax.

8. LeetCode 1011: Capacity to Ship Packages in D Days - Recognize the Feasibility Function

The same pattern as problem 7, with a different feasibility function. Given package weights in order, find the minimum ship capacity to deliver everything in d days.

Search space: [max(weights), sum(weights)]. The lower bound is max(weights) because the heaviest package must fit in one trip. The upper bound is sum(weights) because one day handles everything. The feasibility check: simulate greedy loading. If the next package exceeds capacity, start a new day.

Problems 7 and 8 together cement binary-search-on-answer. The problems look different; the structure is identical. Recognize the monotonic feasibility function, and the rest is the same loop from problem 2.

9. LeetCode 162: Find Peak Element - No Sorted Order Required

A peak element is strictly greater than its neighbors. Find any peak index. The array has no two adjacent equal elements.

There is no global sorted order. So why does binary search work?

Comparing nums[mid] to nums[mid + 1] tells you which side contains a peak, always. If nums[mid] < nums[mid + 1], the slope rises to the right. Either mid + 1 is a peak, or the slope keeps rising and a peak sits further right. Either way, no peak can be left of mid. If nums[mid] > nums[mid + 1], the same logic applies leftward.

def findPeakElement(nums):
    lo, hi = 0, len(nums) - 1
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if nums[mid] < nums[mid + 1]:
            lo = mid + 1
        else:
            hi = mid
    return lo

Local comparison replaces global sort. This is the hardest conceptual leap in the standard binary search curriculum. The moment it clicks, you will immediately think of three other problems it applies to.

10. LeetCode 4: Median of Two Sorted Arrays - Partition, Not Merge

The hard one. Merging both arrays takes O(m+n). The problem asks for O(log(m+n)).

The median is a partition point. Split both arrays so the combined left half holds exactly (m + n) // 2 elements, and the max of the left halves is no greater than the min of the right halves. Binary search on the cut position in the shorter array; the cut in the longer array follows directly.

This is the most conceptually distinct binary search problem in common interview circulation. You are not searching for an element or a threshold. You are searching for a valid partition across two arrays simultaneously. Most interviews cap out at problems 7 or 8. If you can produce this one cold, your template is solid.

Binary Search Pattern Map

Problem	What It Teaches
704	Loop invariant, exit condition, `mid` overflow
278	Leftmost boundary, boundary-search template
35	`lo` semantics on exit without a match
153	Compare to `hi`, rotated array elimination
33	Identify sorted half, then range check
74	2D to 1D index transformation
875	Search on a constructed answer space
1011	Greedy feasibility function plus binary search
162	Local comparison replaces global sort
4	Partition search across two arrays

Knowing the Pattern Is Not the Same as Running It Live

There is a gap between recognizing these patterns on a blog and producing them under pressure. The logic in problem 278 that looks obvious here will not feel obvious when you explain it live. SpaceComplexity runs voice-based mock interviews that surface exactly this gap: the moment where you know the structure but cannot articulate which half you eliminated, or why.

When stuck, go back to the invariant. If you cannot state what property [lo, hi] maintains at every step, you have a guess, not a solution.