Binary Search Pattern: More Than Just Finding a Number

Most developers learn binary search as "find a target in a sorted array." That version is useful, but it is only the beginning. The deeper pattern is about searching over a space where the answer changes predictably from false to true.

Once you understand that, binary search stops being a memorized snippet and becomes a tool you can apply to a surprising number of problems.

The Core Requirement

Binary search works when the search space has a monotonic property.

That means once some condition becomes true, it stays true. Or once it becomes false, it stays false.

Examples:

• numbers in a sorted array
• first bad version in a release sequence
• minimum eating speed that finishes bananas in time
• smallest capacity that ships packages within d days

Classic Binary Search

def binary_search(nums: list[int], target: int) -> int:
    left, right = 0, len(nums) - 1

    while left <= right:
        mid = left + (right - left) // 2

        if nums[mid] == target:
            return mid
        if nums[mid] < target:
            left = mid + 1
        else:
            right = mid - 1

    return -1

The loop invariant is the important part: if the target exists, it must stay inside [left, right].

Boundary Search

Many interview problems do not ask "is it present?" They ask:

• first occurrence
• last occurrence
• lower bound
• upper bound

That changes how you move the pointers when you find a valid answer.

Example: first index where nums[i] >= target.

def lower_bound(nums: list[int], target: int) -> int:
    left, right = 0, len(nums)

    while left < right:
        mid = left + (right - left) // 2

        if nums[mid] < target:
            left = mid + 1
        else:
            right = mid

    return left

This half-open interval style, [left, right), is extremely clean for boundary problems.

Binary Search on the Answer

This is the version that feels magical at first.

Suppose the problem asks:

What is the smallest value x such that a condition becomes possible?

Then you can binary search over possible values of x.

Example: Koko Eating Bananas.

def min_eating_speed(piles: list[int], h: int) -> int:
    def can_finish(speed: int) -> bool:
        hours = 0
        for pile in piles:
            hours += (pile + speed - 1) // speed
        return hours <= h

    left, right = 1, max(piles)

    while left < right:
        mid = left + (right - left) // 2
        if can_finish(mid):
            right = mid
        else:
            left = mid + 1

    return left

The monotonic property is: if Koko can finish at speed x, then she can also finish at any speed greater than x.

Common Pitfalls

• Using binary search on data that is not truly monotonic
• Mixing inclusive and half-open interval styles in the same function
• Returning mid too early in boundary problems
• Infinite loops caused by incorrect pointer updates

Pick one template per problem and stay consistent.

How to Recognize It Fast

These phrases are strong hints:

• "smallest value such that..."
• "minimum capacity to..."
• "first index where..."
• "maximum possible value while..."

Whenever you see a yes/no feasibility check over an ordered search space, binary search should be on your shortlist.

Complexity

R is the size of the value range you are searching.

Practice These Next

• Search Insert Position
• Find First and Last Position of Element in Sorted Array
• First Bad Version
• Koko Eating Bananas
• Capacity To Ship Packages Within D Days

The real unlock is this: binary search is not about arrays. It is about ordered possibilities.