Binary Search: More Than Finding a Number

Binary search is one of those algorithms that sounds simple until you try to write it correctly. The idea is obvious: cut the search space in half each time. But getting the bounds right, avoiding infinite loops, and recognizing when to use it on problems that do not look like search problems at all? That is where things get interesting.

Why O(log n) matters

Linear search checks every element. For an array of 1,000 elements, that is 1,000 comparisons in the worst case. For a million elements, a million comparisons.

Binary search on a sorted array cuts the problem in half with every comparison. For 1,000 elements, that is about 10 comparisons. For a million, about 20. For a billion, about 30.

That is not a small improvement. It is an entirely different growth curve. Any time you see a sorted structure or a monotonic condition, your first thought should be: can I binary search this?

The setup

Binary search works on sorted arrays. You maintain three pointers: lo (the start of the search range), hi (the end), and mid (the middle, where you look).

You compare arr[mid] to your target. If the target is bigger, the answer must be in the right half, so you move lo up. If the target is smaller, the answer is in the left half, so you move hi down. Each step eliminates half the remaining elements.

Walking through it

Let's search for the value 23 in the sorted array [2, 5, 8, 12, 16, 23, 38, 56, 72, 91].

We start with lo = 0 and hi = 9. Watch how the search space shrinks at each step.

Three steps. Out of 10 elements, we only checked 3 of them. If this array had a million elements, we would check at most 20.

Binary search is one of about 60 reusable building blocks that cover the vast majority of coding interview problems. Learning each block on its own, then practicing until you can write it from scratch, is a much better strategy than grinding random problems.

The code

Here is the standard binary search in Python:

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  # not found

A few things to notice:

• We use lo + (hi - lo) // 2 instead of (lo + hi) // 2 to avoid integer overflow. In Python this is not strictly necessary (Python handles big integers natively), but it is a good habit that transfers to languages like Java and C++.
• The loop runs while lo <= hi. When lo passes hi, the search space is empty and we know the target is not in the array.
• We move lo to mid + 1 and hi to mid - 1. Never just mid. This is critical for avoiding infinite loops.

Left-bound and right-bound variants

The basic version finds any occurrence of the target. But what if the array has duplicates and you need the first or last occurrence?

Finding the leftmost (first) occurrence

def left_bound(nums, target):
    lo, hi = 0, len(nums) - 1
    result = -1

    while lo <= hi:
        mid = lo + (hi - lo) // 2

        if nums[mid] == target:
            result = mid       # record it, but keep searching left
            hi = mid - 1
        elif nums[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1

    return result

The key difference: when we find the target, we do not return immediately. Instead, we record the index and keep searching the left half. If there is an earlier occurrence, we will find it.

Finding the rightmost (last) occurrence

def right_bound(nums, target):
    lo, hi = 0, len(nums) - 1
    result = -1

    while lo <= hi:
        mid = lo + (hi - lo) // 2

        if nums[mid] == target:
            result = mid       # record it, but keep searching right
            lo = mid + 1
        elif nums[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1

    return result

Same idea, but when we find the target, we search the right half instead.

Searching on the answer space

This is the variant that trips people up the most, because the problem does not look like a search problem at all. But once you see the pattern, it opens up a whole category of problems.

The idea: instead of searching through an array, you binary search over the possible answers. You define a range of candidate answers, pick the middle one, and check whether it works. If it does, try a smaller (or larger) answer. If it does not, go the other direction.

Example: integer square root

Given a non-negative integer n, find the largest integer x such that x * x <= n.

def integer_sqrt(n):
    lo, hi = 0, n

    while lo <= hi:
        mid = lo + (hi - lo) // 2

        if mid * mid <= n:
            lo = mid + 1    # mid might be the answer, but try bigger
        else:
            hi = mid - 1    # too big, try smaller

    return hi  # hi is the largest value where mid*mid <= n

There is no array here. We are searching the range [0, n] for the largest value that satisfies our condition. The "sorted array" is the sequence of integers 0, 1, 2, ..., n, and the "comparison" is checking whether mid * mid <= n.

The general pattern

Binary search on the answer works whenever:

1. The answer lies in a known range (you can define lo and hi)
2. There is a monotonic condition: if answer x works, then all answers smaller (or larger) than x also work
3. You can check whether a candidate answer is valid in reasonable time

This pattern shows up in problems like:

• Koko eating bananas: binary search on eating speed
• Split array largest sum: binary search on the maximum subarray sum
• Capacity to ship packages within D days: binary search on ship capacity
• Minimum number of days to make M bouquets: binary search on the number of days

In each case, you are not searching an array. You are searching a range of possible answers and using a helper function to check "is this answer good enough?"

def binary_search_on_answer(lo, hi, is_feasible):
    while lo <= hi:
        mid = lo + (hi - lo) // 2

        if is_feasible(mid):
            hi = mid - 1    # try a smaller answer
        else:
            lo = mid + 1    # need a bigger answer

    return lo  # smallest feasible answer

Common mistakes

Binary search bugs are almost always about boundary conditions. Here are the ones that catch people the most.

1. Off-by-one errors with lo and hi.

After checking mid, you need to move lo to mid + 1 or hi to mid - 1. If you set lo = mid or hi = mid, you risk an infinite loop when lo and hi are adjacent, because mid will equal lo and the loop never makes progress.

2. Wrong loop condition.

Using while lo < hi vs while lo <= hi changes the semantics. With lo <= hi, the loop ends when the search space is empty. With lo < hi, it ends when one element remains. Both are valid, but they require different post-loop logic. Pick one convention and stick with it.

3. Integer overflow on mid calculation.

In Java, C++, or other languages with fixed-size integers, (lo + hi) can overflow. Always use lo + (hi - lo) // 2.

4. Forgetting that binary search requires a sorted or monotonic structure.

If the array is not sorted, binary search gives garbage results. This sounds obvious, but in "search on the answer" problems, the monotonicity can be subtle. Always verify that your feasibility condition is monotonic before reaching for binary search.

5. Returning the wrong thing after the loop.

In the standard search, you return mid when you find the target and -1 after the loop. In left-bound/right-bound variants, you return result. In answer-space search, you typically return lo or hi depending on whether you want the smallest feasible or largest feasible answer. Getting this wrong means your code works on most test cases but fails on edge cases.

How to recognize it in interviews

Look for these signals:

• The input is sorted, or the problem involves a monotonic condition
• The problem asks for the first, last, minimum, or maximum value that satisfies some condition
• Brute force would involve checking every value in a range, but you only need one answer
• The problem mentions "minimum possible maximum" or "maximum possible minimum" (these are almost always binary search on the answer)
• A feasibility check exists: given a candidate answer, you can verify whether it works in O(n) or O(n log n) time

If you can frame the problem as "find the boundary between yes and no in a sorted space," binary search applies. For unsorted data, consider hash map patterns or two pointers instead.

Build it into memory

You have seen the algorithm, the variants, the answer-space trick, and the common pitfalls. That is the conceptual understanding part, and it is genuinely the easy half.

The hard half is writing correct binary search code from scratch, six months from now, in a 45-minute interview with someone watching. The difference between "I remember this concept" and "I can produce this code" is real, and it only closes with practice.

Spaced repetition is designed for exactly this. You write the code today, then again tomorrow, then in three days, then a week. Each time from scratch, no peeking. After a few rounds, the pattern is locked in and you can focus your mental energy on the parts of the problem that are actually hard, like figuring out the feasibility function or setting up the search range.

Related posts

• The Two Pointers Pattern - Two pointers on sorted arrays complement binary search and often appear in the same problems
• The Sliding Window Pattern - When the problem involves contiguous subarrays rather than sorted lookups
• Stack-Based Patterns - Monotonic stacks share the same "exploit sorted structure" intuition as binary search

Binary search is one building block. There are roughly 60 of them that cover the vast majority of coding interview problems. Learn each one deeply, drill it until it is automatic, and you stop needing to grind hundreds of random LeetCode problems.

---

Visual Learner? See binary search in action step-by-step with our Binary Search Interactive Visualization.