Binary SearchBinary search

01Why it exists

Reach for it when you see:Sorted data, monotonic predicates, the first position that satisfies a condition, the last one that does not, log n, halving the range, bisect.

02The core idea

Binary search needs exactly one precondition: the data must be monotonic with respect to the question you are asking. A sorted array is the usual form, but the essence is that some condition is false throughout the first part and true throughout the second. Look at the middle element and you know which half holds the answer, so you throw the other half away. Halving each time, n elements are exhausted in ⌈log₂(n+1)⌉ steps, and that is where O(log n) comes from. Getting the real O(log n), though, also requires jumping straight to the middle slot: an array can, whereas a linked list spends O(n) just walking there.

The common mistake is not the idea but the boundaries: whether hi is n or n-1, whether the loop uses < or <=, and whether the update is mid or mid+1 — all three have to match. Two templates are enough to memorise. The closed interval [lo, hi]: hi = n-1, while lo <= hi, both sides ruling mid out with mid ± 1, returning as soon as you find a match. Good for "find any element equal to target". The half-open interval [lo, hi): hi = n, while lo < hi, hi = mid when the condition holds (mid may be the answer, so keep it) and lo = mid + 1 when it does not (mid definitely is not), and when the loop ends lo == hi is the answer. Good for "find the first position that satisfies the condition".

lower_bound is "the first position ≥ target" and upper_bound is "the first position > target" — one equals sign apart in code. What they return is the insertion point in 0..n; when target is absent they do not return −1 but "where it would go if you inserted it", which is why hi has to be allowed to reach n. With those two, many questions compose directly: does target exist, lower < n and a[lower] == target; how many times does it occur, upper − lower; the position of its last occurrence (once you know it exists), upper − 1; "the last one ≤ target", upper − 1; "the last one < target", lower − 1.

Why the half-open version cannot loop forever: mid = (lo + hi) // 2 rounds down, so mid < hi and hi = mid always shrinks the range, while lo = mid + 1 always grows. If you write an update that does not rule mid out, such as lo = mid, then once lo and hi are adjacent mid equals lo and you are stuck. That variant needs rounding up, mid = (lo + hi + 1) // 2, with hi = mid - 1 on the other side. In C++, lo + hi can overflow, so write lo + (hi - lo) / 2.

03The algorithm

1. 1Check that the data is monotonic for your condition: all "no" in the first part, all "yes" in the second. Rewrite the question as "find the first 'yes'".
2. 2Use a half-open interval: lo = 0, hi = n. The answer ranges over 0..n, where n means "everything is a no".
3. 3while lo < hi: mid = (lo + hi) // 2.
4. 4Condition holds (a[mid] ≥ target): hi = mid, keeping mid inside the range. It does not hold: lo = mid + 1, ruling mid out.
5. 5When the loop ends, lo == hi and that is the answer. For upper_bound, change ≥ to >; to test existence, check lo < n and a[lo] == target.

04Interactive demo

The array contains 8 three times. Three modes over the same data and the same target: "find any one" uses the closed interval and stops the moment it hits a match, with no guarantee about which 8 comes back; lower_bound and upper_bound use the half-open interval, and the answer is wherever lo and hi finally meet. Note that hi is exclusive in the half-open version, which is why it can point at n, one past the end of the array.

05Code

Three functions — the classic closed-interval version, lower_bound and upper_bound — plus "first and last occurrence" assembled from them. Python's built-in bisect_left / bisect_right and C++'s std::lower_bound / std::upper_bound are these two bounds, and writing them yourself is what makes their return values obvious.

# Classic version: closed interval [lo, hi]. Returns the index of any matching target, -1 if absent.
def binary_search(nums, target):
    lo, hi = 0, len(nums) - 1
    while lo <= hi:                        # closed interval: lo == hi still leaves one element to check
        mid = (lo + hi) // 2
        if nums[mid] == target:
            return mid
        if nums[mid] < target:
            lo = mid + 1                   # mid has been checked, rule it out
        else:
            hi = mid - 1
    return -1


# lower_bound: the first i with nums[i] >= target (n if there is none).
# Half-open interval [lo, hi). The answer ranges over 0..n, so hi starts at n.
def lower_bound(nums, target):
    lo, hi = 0, len(nums)
    while lo < hi:                         # half-open interval: lo == hi means the range is empty
        mid = (lo + hi) // 2
        if nums[mid] >= target:
            hi = mid                       # mid may be the answer, keep it in the range
        else:
            lo = mid + 1                   # mid definitely is not the answer
    return lo                              # lo == hi by now


# upper_bound: the first i with nums[i] > target. One equals sign away from the above.
def upper_bound(nums, target):
    lo, hi = 0, len(nums)
    while lo < hi:
        mid = (lo + hi) // 2
        if nums[mid] > target:
            hi = mid
        else:
            lo = mid + 1
    return lo


# The two bounds answer the usual questions between them
def first_and_last(nums, target):          # LeetCode 34
    lo = lower_bound(nums, target)
    if lo == len(nums) or nums[lo] != target:
        return [-1, -1]
    return [lo, upper_bound(nums, target) - 1]


if __name__ == "__main__":
    a = [2, 5, 8, 8, 8, 13, 21, 34, 55, 89]
    print(binary_search(a, 8))     # 4 (any one of them)
    print(lower_bound(a, 8))       # 2
    print(upper_bound(a, 8))       # 5
    print(first_and_last(a, 8))    # [2, 4]
    print(lower_bound(a, 9))       # 5 (absent: the insertion point)
    # Built in: bisect.bisect_left is lower_bound, bisect_right is upper_bound

06Practice

• LeetCode 704Binary SearchEasy
• LeetCode 35Search Insert Position (this is lower_bound)Easy
• LeetCode 278First Bad Version (git bisect as a puzzle)Easy
• LeetCode 34Find First and Last Position of Element in Sorted ArrayMedium
• LeetCode 33Search in Rotated Sorted Array (work out which half is sorted)Medium
• LeetCode 162Find Peak Element (binary search on uphill vs. downhill)Medium