Binary search

Problem

Given a sorted array, is a value in it, and where? Scanning from the left costs O(n). The array being sorted is information you are not using: one comparison with the middle element tells you which half can hold the answer and which half cannot. Repeat on the surviving half and a million elements take about twenty comparisons. The same idea applies whenever the data has a hidden order: a rotated array is two sorted runs glued together, and a "good, good, bad, bad, bad" sequence is sorted by the yes-or-no answer even if nothing looks like numbers.

Intuition

It is the number-guessing game. You pick a number between 1 and 100 and say "higher" or "lower" after each guess. Guessing the middle every time is the best strategy because whatever you hear, half of the remaining numbers are gone. After seven guesses at most one number is left.

What makes this safe to code is to say in words what the range promises. In the version used here the range is half-open, from lo up to but not including hi, and it promises "the answer is somewhere in this range, and if no element qualifies the answer is hi". Every line of the loop exists to keep that sentence true while making the range smaller.

Blue cells are the live range, amber is the midpoint just examined and green the final answer. The live range starts at all 10 cells and shrinks every row.

Mechanics

The invariant

Search for the first index whose value is at least the target in the half-open range [lo, hi), starting at lo = 0 and hi = len(nums). The invariant: every index below lo holds a value less than the target, and every index at or above hi holds a value at least the target (or does not exist). The answer therefore sits in [lo, hi].

While lo < hi, take mid = (lo + hi) // 2, which is always inside the range. If nums[mid] < target, then mid and everything below it are too small: set lo = mid + 1. Otherwise mid qualifies and so does everything after it, but something earlier might also qualify: set hi = mid. Both moves keep the invariant, and both shrink the range by at least one element, so the loop ends with lo == hi, and the invariant says that index is the answer.

Finding a value, and why this form is safer

Lower bound does not ask "is this the target?" in the loop. When it ends, check once whether lo is in range and nums[lo] == target. This single shape answers three questions: membership, insertion point (lo itself, even when the value is missing) and first occurrence among duplicates. An early return on nums[mid] == target gives up the last two and invites off-by-one bugs, so use it only for plain membership.

Any monotone yes-or-no test

Nothing above needed numbers. All it used was a predicate ok(i) that is false for a prefix of the indices and true for the rest. Replace nums[mid] < target with not ok(mid) and the loop finds the first true. "First bad version" is exactly that. The next page uses the same loop over answers rather than positions.

Rotated arrays

Rotating a sorted array of distinct values makes two ascending runs, with a drop between them. For any midpoint, at least one of [lo, mid] and [mid, hi] does not contain the drop and is therefore sorted. Test which: if nums[lo] <= nums[mid] the left half is sorted. Then check whether the target lies within that sorted half's bounds; if so keep it, otherwise discard it and keep the other half. To find the minimum, compare nums[mid] with nums[hi]: if the midpoint is larger the drop is to its right, otherwise the minimum is at mid or before it.

Two ascending runs with a drop between them. Amber bars are midpoints the minimum search looked at; green is the minimum it found.

Worked example

Lower bound of 23 in [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]. The range is [lo, hi):

The search stops at index 5, and 23 equals the target, so 23 is present. Searching for 20 instead stops at index 5, the position where 20 would be inserted, and nums[5] is 23, not 20, so it is absent.

Rotated search for 5 in [15, 19, 23, 38, 2, 5, 8, 12]. This is a closed range, so the loop runs while lo <= hi:

The value 5 is at index 5.

Rotated minimum for the same array. Each step compares the midpoint with the right end:

The minimum is 2 at index 4.

Implementation

from bisect import bisect_left


def lower_bound(nums, target):
    lo, hi = 0, len(nums)                        # answer is in [lo, hi]
    while lo < hi:
        mid = (lo + hi) // 2
        if nums[mid] < target:
            lo = mid + 1
        else:
            hi = mid
    return lo


def search(nums, target):
    i = lower_bound(nums, target)
    return i if i < len(nums) and nums[i] == target else -1


def first_true(lo, hi, ok):
    """Smallest i in [lo, hi) with ok(i), or hi if none; ok must be False for a prefix, then True."""
    while lo < hi:
        mid = (lo + hi) // 2
        if ok(mid):
            hi = mid
        else:
            lo = mid + 1
    return lo


def search_rotated(nums, target):
    lo, hi = 0, len(nums) - 1
    while lo <= hi:
        mid = (lo + hi) // 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


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

bisect_left(nums, target) from the standard library is lower_bound; in an interview write the loop out, and use bisect at work. Python integers do not overflow, so (lo + hi) // 2 is safe here; in a fixed-width language write lo + (hi - lo) // 2.

Variations and edge cases

• Last position instead of first. Find the first index greater than the target (nums[mid] <= target moves right) and subtract one. This is bisect_right.
• Matrix as one array. Search indices 0 to rows × cols − 1 and read the cell at divmod(mid, cols).
• Search for a window, not an element. For the k closest elements, search the left edge of the window over [0, n − k] and compare how far x is from nums[mid] and nums[mid + k].
• Duplicates in a rotated array. When nums[lo] == nums[mid] == nums[hi] you cannot tell which half is sorted, so shrink both ends by one; the worst case degrades to O(n).
• Edge cases: an empty array (the loop never runs and lower bound returns 0), a target smaller than everything (index 0), larger than everything (index n), a single element, duplicates, and a rotation by zero, where the array is simply sorted.

Complexity and tradeoffs

• Time: O(log n). The range loses at least half its elements per step. This array of 10 needed 3 steps.
• Space: O(1) for the loop.
• Baseline. A linear scan is O(n) and needs no ordering. If you search once in unsorted data, scanning beats sorting first (O(n log n)); binary search wins when the data is sorted already or searched many times.
• When it fails. The data must have order that a single comparison can exploit. Unsorted data, or a predicate that flips more than once, breaks the invariant. A rotated array with many duplicates loses the guarantee that one half is sorted.

Problems

The home problems are the plain search, the first-true predicate, the search over a flattened matrix, the rotated variants, a time-keyed store that searches the last entry at or before a time, and the mountain array, which needs the loop twice. Every one is a version of "keep the invariant, shrink the range".

Easy

• 35. Search Insert Position NeetCode 250
  The answer is the first index whose value is at least the target, which is exactly where a lower-bound search stops.
• 278. First Bad Version Grind 169
  Versions are good then bad, so search for the first true of a monotone predicate.
• 374. Guess Number Higher or Lower NeetCode 250
  The feedback says which half holds the hidden number, so the range halves after every guess.
• 704. Binary Search Grind 169 NeetCode 150 NeetCode 250
  Keep a closed range that must contain the target and halve it by comparing the midpoint.

Medium

• 33. Search in Rotated Sorted Array Blind 75 Grind 169 NeetCode 150 NeetCode 250
  At every midpoint one half is sorted, so check whether the target lies inside that sorted half and discard the other.
• 74. Search a 2D Matrix Grind 169 NeetCode 150 NeetCode 250
  Treat the matrix as one sorted array of rows times columns and map each midpoint back to a row and column.
• 81. Search in Rotated Sorted Array II NeetCode 250
  Search like the rotated case, but when the low, middle and high values are equal you cannot tell which half is sorted, so shrink both ends by one.
• 153. Find Minimum in Rotated Sorted Array Blind 75 Grind 169 NeetCode 150 NeetCode 250
  Compare the midpoint with the right end: if it is larger the minimum lies to its right, otherwise at or to its left.
• 658. Find K Closest Elements Grind 169 NeetCode 250
  Binary search for the left edge of the length-k window, comparing the distances of x to the window's two possible ends.
• 981. Time Based Key-Value Store Grind 169 NeetCode 150 NeetCode 250
  Timestamps arrive in increasing order per key, so binary search for the last one at or before the query time.

Hard

• 1095. Find in Mountain Array NeetCode 250
  Binary search for the peak, then search the ascending side first and the descending side second, each with its own comparison.

Also uses this pattern

These problems have a different home page, but this idea is part of their solution.

• 69. Sqrt(x) Easy
• 300. Longest Increasing Subsequence Medium
• 528. Random Pick with Weight Medium
• 4. Median of Two Sorted Arrays Hard
• 1235. Maximum Profit in Job Scheduling Hard

Connections

The loop-halving analysis comes from the complexity page. The next page applies the same first-true loop to the space of possible answers, which is the form most hard binary-search interview problems take. Trees bring the same halving to linked structures, where a binary search tree is a binary search you can update.

Check yourself

References

• Cormen, Leiserson, Rivest and Stein, Introduction to Algorithms: binary search as an exercise in loop invariants, and the divide-and-conquer chapter.
• Knuth, The Art of Computer Programming, volume 3, section 6.2.1, on searching an ordered table; it notes that the first binary search was published in 1946 but a bug-free one only in 1962.
• Bentley, Programming Pearls, column 4: writing a correct binary search with an invariant.
• Sedgewick and Wayne, Algorithms, section 3.1: binary search in an ordered symbol table.
• Skiena, The Algorithm Design Manual: the section on binary search and bisection.
• The NeetCode roadmap and the Blind 75, Grind 169, NeetCode 150 and NeetCode 250 lists, used as the index of topics and problems.