Classic Binary Search

You have a sorted array and you need to find a target value. A linear scan checks every element and takes $O(n)$ time. Binary search does it in $O(\log n)$ by exploiting the sorted order: each comparison eliminates half of the remaining candidates.

That halving insight is the engine of the algorithm. An array of one million elements requires at most 20 comparisons. One billion elements? Only 30. The search space shrinks so aggressively that binary search feels almost unfair.

The lo <= hi Template for Exact Search

The most common binary search template looks for an exact match. You maintain two pointers, lo and hi, that define the range of indices still under consideration. At each step you compute the midpoint, compare the element there to the target, and shrink the range accordingly.

If the element at mid equals the target, you are done. If it is less than the target, the target must be to the right, so you set lo = mid + 1. If it is greater, the target must be to the left, so you set hi = mid - 1. The loop continues while lo <= hi, that is, while there is at least one element left to check. If the loop ends without finding the target, you return -1.

Walking Through an Example

Let us search for 7 in the array [1, 3, 5, 7, 9, 11].

We start with lo = 0 and hi = 5. The midpoint is (0 + 5) // 2 = 2, and nums[2] = 5. Since 5 < 7, the target is to the right, so we set lo = 3.

Now lo = 3 and hi = 5. The midpoint is (3 + 5) // 2 = 4, and nums[4] = 9. Since 9 > 7, the target is to the left, so we set hi = 3.

Now lo = 3 and hi = 3. The midpoint is 3, and nums[3] = 7. That is our target. We return index 3.

Three comparisons to find the answer in a six-element array. In a sorted array of a million elements, this process would take at most 20 steps.

Code: Basic Binary Search

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

This is clean and correct, but every detail matters. Change lo <= hi to lo < hi and you will miss the case where the target is the last remaining element. Change hi = mid - 1 to hi = mid and you risk an infinite loop when lo == hi. Binary search is famously easy to get wrong in the details.

The Off-by-One Minefield

The most common source of binary search bugs is the relationship between the loop condition, the update rules, and what lo and hi represent.

In the exact search template above, lo and hi are both inclusive: they define a closed interval [lo, hi]. The loop runs while lo <= hi because a single-element range is still worth checking. When we rule out mid, we move past it: lo = mid + 1 or hi = mid - 1.

In the boundary search templates below, hi represents an exclusive upper bound or a candidate boundary, and the loop runs while lo < hi. The key difference is that when we narrow toward a boundary, we sometimes set hi = mid (not mid - 1) because mid itself might be the answer.

The rule of thumb: decide up front whether your interval is [lo, hi] or [lo, hi), commit to it, and let that decision dictate your loop condition and updates. Once you fix the invariant, the rest follows mechanically.

Lower Bound: First Element >= Target

Many problems do not ask "is this value present?" but rather "where would this value go?" or "what is the first element at least as large as the target?" This is the lower bound, also known as bisect_left in Python.

The template uses lo < hi as its loop condition and sets hi = mid (instead of mid - 1) when the middle element is greater than or equal to the target. The reasoning: if nums[mid] >= target, then mid might be the answer, so we cannot exclude it. We narrow the window to [lo, mid]. When nums[mid] < target, we know mid is too small, so we set lo = mid + 1.

When the loop exits, lo == hi, and that position is the first index where nums[index] >= target. If every element is smaller than the target, lo ends up at len(nums), indicating the target would be inserted at the end.

Walking Through Lower Bound

Let us find the lower bound of 5 in [1, 3, 5, 5, 5, 7, 9].

We start with lo = 0 and hi = 7 (the length of the array, since hi is exclusive in this template).

Mid = (0 + 7) // 2 = 3. nums[3] = 5. Since 5 >= 5, this could be our answer, but there might be an earlier 5. Set hi = 3.

Mid = (0 + 3) // 2 = 1. nums[1] = 3. Since 3 < 5, set lo = 2.

Mid = (2 + 3) // 2 = 2. nums[2] = 5. Since 5 >= 5, set hi = 2.

Now lo == hi == 2. The loop ends. Index 2 is the first position where the value is >= 5, which is indeed where the run of 5s begins.

Code: Lower Bound

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

For the upper bound (first element strictly greater than the target, equivalent to bisect_right), the only change is the comparison: use nums[mid] <= target instead of nums[mid] < target. This makes the search skip past elements equal to the target, landing on the first element that exceeds it.

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

Together, lower_bound and upper_bound let you find the range of all elements equal to the target: it spans from lower_bound(target) to upper_bound(target) - 1. If those two values are equal, the target is not present.

Search in a 2D Matrix

Consider LeetCode 74 (Search a 2D Matrix), which gives you an $m \times n$ matrix where each row is sorted and the first element of each row is greater than the last element of the previous row. The entire matrix, read row by row, forms one long sorted sequence.

The trick is to treat the matrix as a flat sorted array of length $m \cdot n$ and run a standard binary search on it. The only question is how to convert a flat index to row and column coordinates. If the flat index is mid, then the row is mid // n and the column is mid % n, where n is the number of columns.

def search_matrix(matrix, target):
    m, n = len(matrix), len(matrix[0])
    lo, hi = 0, m * n - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        val = matrix[mid // n][mid % n]
        if val == target:
            return True
        elif val < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return False

This runs in $O(\log(m \cdot n))$ = $O(\log m + \log n)$ time. No need for a two-phase search (find the row, then search within it). One binary search does it all.

The "Decide Your Invariant Up Front" Principle

The single most useful binary search discipline is this: before writing any code, state in plain language what lo and hi represent and what is true about them throughout the search.

For exact search: "lo and hi are the inclusive bounds of the region that might contain the target." This forces lo <= hi as the loop condition and mid +/- 1 as the updates, because once you check mid and it is not the target, you exclude it.

For lower bound: "lo is the smallest index that could be the answer; hi is the smallest index that is definitely too high." This forces lo < hi as the loop condition, hi = mid when mid could be the answer, and lo = mid + 1 when it cannot.

If you ever find yourself confused about whether to use <= or <, or mid - 1 or mid, go back to the invariant. The correct choice is whichever one maintains the invariant you stated. This single habit eliminates the majority of binary search bugs.

Python's bisect Module

Python's standard library provides the bisect module, which implements lower and upper bound searches so you do not have to write them by hand.

bisect.bisect_left(a, x) returns the leftmost index where x could be inserted to keep the list sorted. This is the lower bound (first element >= x). bisect.bisect_right(a, x) (or equivalently bisect.bisect(a, x)) returns the rightmost such index, the upper bound (first element > x).

These are invaluable in contests and interviews where you want to avoid writing binary search from scratch. For example, to check if a value exists in a sorted list: i = bisect_left(a, x); found = i < len(a) and a[i] == x.

Sqrt(x) and Valid Perfect Square

LeetCode 69 (Sqrt(x)) asks for the largest integer whose square is less than or equal to x. The closely related LeetCode 367 (Valid Perfect Square) asks whether any integer squares to exactly x. Both are binary search on the answer space rather than on an array.

For sqrt, the answer lies somewhere in [0, x]. You binary search for the largest value whose square does not exceed x. This is essentially a lower/upper bound search where the "sorted array" is the sequence of perfect squares 0, 1, 4, 9, 16, ...

def my_sqrt(x):
    lo, hi = 0, x
    while lo <= hi:
        mid = (lo + hi) // 2
        if mid * mid <= x:
            lo = mid + 1
        else:
            hi = mid - 1
    return hi

When the loop ends, hi is the largest integer whose square is <= x. For Valid Perfect Square, check whether hi * hi == x after the search.

Find K Closest Elements

With LeetCode 658, you are given a sorted array and must find the k elements closest to a target value. The key insight is that the answer is always a contiguous window of size k within the array. You binary search for the left boundary of that window.

The search space for the left boundary is [0, len(nums) - k]. At each midpoint, compare the distance from nums[mid] to the target versus the distance from nums[mid + k] to the target. If the right side is closer (or equally close), shift the window right; otherwise, keep the current left boundary as a candidate.

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

This runs in $O(\log(n - k) + k)$ time: logarithmic to find the window, plus linear to extract it.

Time Based Key-Value Store

The problem LeetCode 981 asks you to store key-value pairs with timestamps and retrieve the value for a key at the largest timestamp less than or equal to a given query time. Since timestamps are inserted in increasing order, each key's timestamp list is already sorted, making binary search a natural fit.

For each key, maintain a list of (timestamp, value) pairs. On a get query, binary search that list for the rightmost timestamp <= the query time. This is an upper bound search: find the first timestamp strictly greater than the query, then step back by one.

import bisect

class TimeMap:
    def __init__(self):
        self.store = {}

    def set(self, key, value, timestamp):
        self.store.setdefault(key, []).append((timestamp, value))

    def get(self, key, timestamp):
        if key not in self.store:
            return ""
        pairs = self.store[key]
        i = bisect.bisect_right(pairs, (timestamp, chr(127)))
        return pairs[i - 1][1] if i > 0 else ""

The bisect_right call with a high sentinel character finds the insertion point just past any entry with the query timestamp. Stepping back one position gives the largest timestamp that does not exceed the query.

Random Pick with Weight

Take LeetCode 528, which asks you to randomly pick an index where the probability of picking index i is proportional to w[i]. The approach is to build a prefix sum array, generate a random number in [1, total_weight], and binary search for where that number lands in the prefix sums.

The prefix sum array turns the weights into consecutive ranges. For weights [1, 3, 2], the prefix sums are [1, 4, 6], representing ranges [1,1], [2,4], [5,6]. A random number in [1, 6] maps to the correct index via a lower bound search.

import bisect
import random

class Solution:
    def __init__(self, w):
        self.prefix = []
        running = 0
        for weight in w:
            running += weight
            self.prefix.append(running)

    def pick_index(self):
        target = random.randint(1, self.prefix[-1])
        return bisect.bisect_left(self.prefix, target)

The bisect_left call finds the first prefix sum >= the random target, which is exactly the index whose weight range contains that target. Initialization is $O(n)$; each pick is $O(\log n)$.

Single Element in a Sorted Array

For LeetCode 540, you are given a sorted array where every element appears exactly twice except for one element that appears once. You need to find the single element in $O(\log n)$ time.

The trick is to observe the pairing structure. Before the single element, pairs start at even indices: nums[0] == nums[1], nums[2] == nums[3], and so on. After the single element, pairs shift to start at odd indices. Binary search on this parity invariant to find where the shift happens.

At each midpoint, check whether mid and its pair-neighbor hold equal values. If mid is even, its partner should be mid + 1; if mid is odd, its partner should be mid - 1. If the pairing holds, the single element is to the right; otherwise, it is to the left.

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

By snapping mid to an even index, we always compare the start of a would-be pair. If the pair is intact, the single element must be later in the array, so we jump past both elements with lo = mid + 2. Otherwise, the disruption is at or before mid, so we set hi = mid.

Complexity Analysis

Time: $O(\log n)$ for all variants. Each iteration halves the search space, so the number of iterations is at most ceil(log2(n)).

Space: $O(1)$. Binary search uses only a constant number of variables regardless of input size. Recursive implementations use $O(\log n)$ stack space, but the iterative versions shown here avoid that.

Binary search is deceptively simple in concept, halve the search space and repeat, but the implementation details around loop conditions, boundary updates, and invariants are where most bugs hide. Master the two templates (exact search with lo <= hi, boundary search with lo < hi), commit to stating your invariant before you code, and the off-by-one errors will take care of themselves.

Recognizing this pattern

You're probably looking at classic binary search when:

• The input is a sorted array (or a sorted view of one), and you need a lookup, first/last index, or insertion point.
• You can phrase the question as "is the target here, to the left, or to the right?" at each midpoint.
• The problem asks for $O(\log n)$, and anything slower is unacceptable.
• You need an insertion index for an element not present (lower_bound / upper_bound semantics).

Common templates:

• Exact-match search (lo <= hi): return the matching index or -1; loop ends when lo > hi. Example: Binary Search.
• Lower bound (lo < hi): first index where nums[i] >= target; useful for "insert position" queries. Example: Search Insert Position.
• First and last occurrence: two boundary searches, one for the leftmost match and one for the rightmost. Example: Find First and Last Position of Element in Sorted Array.
• Search on a sorted matrix: treat the matrix as a flat sorted array and divmod the midpoint into (row, col). Example: Search a 2D Matrix.
• Peak finding on a unimodal array: compare nums[mid] with nums[mid+1] to decide which half contains the peak. Example: Find Peak Element.