Binary Search Beyond the Sorted Array

Start with a search invariant

Binary search applies when a predicate changes monotonically over an ordered domain. Each comparison discards half the remaining candidates, reducing n possibilities to one in O(log n) checks. Before writing code, decide whether you seek an exact match, the first valid position, or the last valid position; these problems need different update rules.

A reliable lower-bound template

Lower bound returns the first index whose value is at least the target. Use a half-open interval [left, right): values before left are known to be too small, and values at or after right are outside the search range.

def lower_bound(nums, target):
    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

The returned index can equal len(nums) if every value is smaller than the target. If you need to confirm the target exists, check both that the index is in range and that its value equals the target.

Binary search on the answer

Sometimes the array is not sorted, but feasibility is monotonic. Suppose a shipping problem asks for the smallest capacity that can deliver all packages within a deadline. If a capacity works, every larger capacity also works. Binary-search the capacity, and write a helper that greedily counts the days required for one candidate.

Choose low and high bounds that include the solution. Then search for the first feasible value using the same lower-bound structure, replacing nums[mid] < target with the problem's feasibility test. The overall cost is the number of binary-search checks times the cost of one feasibility evaluation.

Common off-by-one pitfalls

• Use midpoint left + (right - left) // 2 for languages where integer overflow is possible.
• Ensure every loop iteration moves at least one boundary.
• Do not mix inclusive and half-open interval conventions in the same solution.
• Test empty input, one element, all values satisfying the predicate, and none satisfying it.
• For floating-point search, define a precision or iteration limit rather than expecting exact equality.