Binary Search: Lower/Upper Bound, Binary Search on the Answer, and Off-by-One Traps

Introduction

Binary search finds a value in a sorted array in O(log n) comparisons by repeatedly discarding the half that cannot contain it. For a million elements that is at most 20 comparisons, against up to a million for a linear scan.

The idea fits in one sentence, and yet it is notoriously easy to get wrong. Jon Bentley reported that most professional programmers he asked could not write a correct binary search on the first try, and the binary search in Java’s standard library had an integer overflow bug in its midpoint calculation for about nine years before it was found in 2006. The bugs are almost never in the idea; they are in the bounds: < vs <=, mid vs mid - 1, len(arr) vs len(arr) - 1.

In my own interview practice, the solutions that failed were rarely wrong in approach. They failed on an array of length 1, on a target smaller than every element, or by looping forever on two elements. So instead of memorizing five variants, this guide builds them all from one idea: a monotonic condition and an invariant on what left and right mean.

---

Classic Binary Search

Tracing it by hand

Find 7 in [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]   (indices 0..9)

left=0 right=9  mid=4  arr[4]=9  > 7  -> right = 3
left=0 right=3  mid=1  arr[1]=3  < 7  -> left  = 2
left=2 right=3  mid=2  arr[2]=5  < 7  -> left  = 3
left=3 right=3  mid=3  arr[3]=7 == 7  -> found at index 3

Implementation

def binary_search(arr, target):
    left, right = 0, len(arr) - 1      # invariant: if target exists, it is in arr[left..right]

    while left <= right:               # range is non-empty
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1             # arr[mid] and everything left of it are too small
        else:
            right = mid - 1            # arr[mid] and everything right of it are too large

    return -1                          # range became empty

arr = [1, 3, 5, 7, 9, 11, 13, 15]
print(binary_search(arr, 7))   # 3
print(binary_search(arr, 10))  # -1

Every line here follows from the invariant in the first comment. The range is inclusive, so the loop runs while it has at least one element (left <= right), and each branch removes mid itself, because we have already checked it (mid + 1, mid - 1). If the loop were left < right, a range of exactly one element would never be examined, and searching [5] for 5 would return -1.

Why it always terminates: each iteration either returns or moves left right of mid or right left of mid, so the range shrinks by at least one element every time.

Why O(log n)

Each step halves the remaining range, so after k steps at most n / 2^k elements remain. The loop ends when that drops below 1, which takes about log₂(n) steps: 10 for n = 1,000, 20 for n = 1,000,000, 30 for n = 10⁹.

That comparison is only fair if the data is already sorted. Sorting costs O(n log n), so sorting once to answer a single query is slower than one linear scan. Binary search pays off when you sort once and query many times, or when the data arrives sorted — database indexes, log files ordered by timestamp, version histories.

Recursive version

def binary_search_recursive(arr, target, left, right):
    if left > right:
        return -1
    mid = (left + right) // 2
    if arr[mid] == target:
        return mid
    if arr[mid] < target:
        return binary_search_recursive(arr, target, mid + 1, right)
    return binary_search_recursive(arr, target, left, mid - 1)

arr = [1, 3, 5, 7, 9]
print(binary_search_recursive(arr, 7, 0, len(arr) - 1))  # 3

The recursion depth is only O(log n), so stack overflow is not a concern. The iterative version is still the usual choice: it is the same logic without the function-call overhead, and it is easier to extend to the variants below.

---

Lower Bound and Upper Bound

The classic version answers “is x here, and where?” Real problems more often ask “where does x start?”, “how many x are there?”, or “where would x go?”. Those are lower and upper bound.

Thinking in terms of a condition

Take arr = [1, 2, 2, 2, 3, 4, 5] and the condition arr[i] >= 2:

index:      0  1  2  3  4  5  6
value:      1  2  2  2  3  4  5
arr[i]>=2:  F  T  T  T  T  T  T
               ^ lower_bound(2) = first T = 1

The condition is false for a prefix and true for the rest. Binary search finds the boundary: the first index where it becomes true. Every variant in this article is this same search with a different condition.

Lower bound: first index with arr[i] >= x

def lower_bound(arr, x):
    left, right = 0, len(arr)          # half-open: answer is in [left, right]; right=len means "none"
    while left < right:
        mid = (left + right) // 2
        if arr[mid] < x:               # condition false at mid -> boundary is to the right
            left = mid + 1
        else:                          # condition true at mid -> mid might be the first true
            right = mid
    return left

arr = [1, 2, 2, 2, 3, 4, 5]
print(lower_bound(arr, 2))   # 1  (first 2)
print(lower_bound(arr, 3))   # 4
print(lower_bound(arr, 0))   # 0  (every element is >= 0)
print(lower_bound(arr, 10))  # 7  (no element is >= 10, returns len(arr))

Note the differences from the classic version, all driven by the new invariant:

• right starts at len(arr), not len(arr) - 1, because “no element qualifies” is a legitimate answer and needs its own position.
• The loop is left < right: when they meet, the range holds exactly one candidate, and that is the answer. There is no early return.
• right = mid, not mid - 1, because mid satisfied the condition and might be the first one that does.

Upper bound: first index with arr[i] > x

The only change is the condition: < becomes <=.

def upper_bound(arr, x):
    left, right = 0, len(arr)
    while left < right:
        mid = (left + right) // 2
        if arr[mid] <= x:
            left = mid + 1
        else:
            right = mid
    return left

arr = [1, 2, 2, 2, 3, 4, 5]
print(upper_bound(arr, 2))  # 4  (first element after the 2s)
print(upper_bound(arr, 5))  # 7  (len(arr))

What they are used for

arr = [1, 2, 2, 2, 3, 4, 5]

# Count occurrences of x
count_2 = upper_bound(arr, 2) - lower_bound(arr, 2)          # 3

# Does x exist? (lower bound alone is not enough — check the value)
i = lower_bound(arr, 6)
exists = i < len(arr) and arr[i] == 6                         # False

# Count elements in [lo, hi]
count_in_range = upper_bound(arr, 4) - lower_bound(arr, 2)    # 5  (2, 2, 2, 3, 4)

# Count elements >= x, and elements <= x
count_ge_3 = len(arr) - lower_bound(arr, 3)                   # 3
count_le_3 = upper_bound(arr, 3)                              # 5

The existence check is where lower bound bites people: it returns a valid-looking index even when x is absent (the position where x would go), and len(arr) when x is larger than everything. Indexing arr[i] without the i < len(arr) guard is an IndexError waiting for the test case where the target is the largest value.

Library versions

Python and C++ both ship these, and in real code you should use them.

import bisect

arr = [1, 2, 3, 5, 6, 7]
bisect.bisect_left(arr, 4)    # 3 -> lower bound
bisect.bisect_right(arr, 4)   # 3 -> upper bound (same when 4 is absent)
bisect.insort(arr, 4)         # [1, 2, 3, 4, 5, 6, 7], keeps it sorted

# Python 3.10+: search by key without building a separate list
people = [("ann", 25), ("bob", 31), ("cy", 40)]              # sorted by age
bisect.bisect_left(people, 30, key=lambda p: p[1])            # 1

insort finds the position in O(log n), but inserting into a Python list still shifts elements and is O(n). For many insertions into a large sorted collection, a balanced structure (sortedcontainers.SortedList in Python, std::set in C++) is the better tool.

#include <algorithm>
#include <vector>

std::vector<int> arr = {1, 2, 2, 2, 3, 4, 5};
auto lo = std::lower_bound(arr.begin(), arr.end(), 2);   // first >= 2
auto hi = std::upper_bound(arr.begin(), arr.end(), 2);   // first > 2
auto count = hi - lo;                                     // 3
bool found = std::binary_search(arr.begin(), arr.end(), 2);

In C++, calling std::lower_bound on a std::set compiles and gives the right answer, but it is O(n): set iterators are not random access, so the generic algorithm has to walk them. Use the member function s.lower_bound(x), which is O(log n). I have seen this turn an otherwise correct solution into a time limit exceeded.

---

Binary Search on the Answer (Parametric Search)

This is where binary search stops being about arrays. Many optimization problems have the shape “find the smallest X such that something is possible” or “the largest X such that something still works”. If you can check a single candidate X quickly, and the answer to “does X work?” is monotonic in X, you can binary search over X itself.

"What is the minimum speed?"  ->  "Is speed k fast enough?"   (yes/no, monotonic in k)

speed:      1  2  3  4  5  6  7  ...
fast enough F  F  F  T  T  T  T      -> answer = first T

The two things to verify before using it:

1. Monotonicity. If speed 4 is enough, every speed above 4 must be enough too. If that fails, binary search returns a wrong answer without any error.
2. Bounds. left must be a value you are sure is at or below the answer, and right at or above it. Getting the bounds too tight silently cuts off the real answer.

Example: cutting trees (largest height that still works)

Given tree heights and a required amount of wood, find the highest saw height H such that cutting everything above H yields at least target. Raising H never gives more wood, so “H yields enough” is true for a prefix of heights and false after — monotonic.

def wood_at(trees, h):
    return sum(t - h for t in trees if t > h)

def max_cut_height(trees, target):
    left, right = 0, max(trees)       # H=0 gives all the wood; H=max gives none
    best = 0
    while left <= right:
        mid = (left + right) // 2
        if wood_at(trees, mid) >= target:
            best = mid                # mid works; try higher
            left = mid + 1
        else:
            right = mid - 1           # too high; go lower
    return best

trees = [20, 15, 10, 17]
print(max_cut_height(trees, 7))       # 15 -> 5 + 0 + 0 + 2 = 7

Total cost: O(n log(max height)). With heights up to 10⁹ that is about 30 checks of O(n) each, compared with trying every height, which is hopeless.

This version keeps a separate best variable and uses the inclusive template. That is a deliberate choice for “largest X that works”: it avoids the infinite-loop trap described in the next section.

Example: minimum speed to arrive on time (smallest value that works)

This is LeetCode 1870. You ride trains in order; each ride except the last must end on a whole hour, because the next train departs on the hour. Find the minimum integer speed that gets you there within hour, or -1.

def min_speed_on_time(dist, hour):
    if hour <= len(dist) - 1:          # every ride but the last takes >= 1 hour
        return -1

    def on_time(speed):
        total = 0
        for d in dist[:-1]:
            total += (d + speed - 1) // speed   # integer ceiling: wait for the next hour
        total += dist[-1] / speed               # last ride: no waiting
        return total <= hour

    left, right = 1, 10**7             # upper bound stated by the problem's constraints
    while left < right:
        mid = (left + right) // 2
        if on_time(mid):
            right = mid                # mid works; the answer is mid or smaller
        else:
            left = mid + 1
    return left

print(min_speed_on_time([1, 3, 2], 2.7))   # 3

Two details that tend to cost submissions on this problem:

• The impossibility check. Without it, the search converges to 10**7 and returns that instead of -1. Checking up front is clearer than checking on_time(right) at the end.
• Integer ceiling. (d + speed - 1) // speed avoids math.ceil(d / speed), which goes through floating point. For values this size it happens to be safe, but the integer form is correct for any size and is a good habit.

The same template solves Koko Eating Bananas (875), Capacity to Ship Packages (1011) and Split Array Largest Sum (410): write the feasible(x) check, prove it is monotonic, pick safe bounds, and search.

Choosing the bounds is usually a matter of asking what the answer can never go below and never needs to exceed. For Koko, eating speed 1 is the slowest meaningful speed and max(piles) is always fast enough, because at that speed every pile takes exactly one hour. For shipping packages, the capacity must be at least max(weights) (otherwise the heaviest package never fits) and sum(weights) always works (ship everything on day one). Deriving the bounds from the problem like this is safer than copying a constant such as 10**9: a lower bound that is too small is harmless, but a lower bound that is too large or an upper bound that is too small cuts off the true answer and produces a wrong result with no error.

Most of the running time is spent inside feasible, not in the search itself, so that is where optimization effort belongs. The search contributes a factor of about 30 for bounds up to 10⁹; if the check is O(n log n) because it sorts on every call, moving the sort outside the search is often the difference between passing and timing out.

---

The Bugs That Actually Happen

Mixing conventions

The inclusive template (left <= right, right = mid - 1) and the half-open template (left < right, right = mid) are each correct on their own. Combining parts of both is where most bugs come from:

# Broken: inclusive loop with half-open update
while left <= right:
    mid = (left + right) // 2
    if arr[mid] < x:
        left = mid + 1
    else:
        right = mid        # when left == right == mid, nothing changes -> infinite loop

Pick one template per problem and write the invariant as a comment before writing the loop.

The infinite loop when searching for the last true

When you want the last position where a condition holds and you write left = mid, the floor midpoint can get stuck:

# left=3, right=4 -> mid=3 -> condition true -> left = 3 -> same state forever
while left < right:
    mid = (left + right) // 2
    if ok(mid):
        left = mid
    else:
        right = mid - 1

With two candidates left, (left + right) // 2 rounds down to left, and left = mid makes no progress. The fix is to round up: mid = (left + right + 1) // 2. The rule of thumb: if the branch that keeps mid assigns it to left, round up; if it assigns it to right, round down. Or use the inclusive template with a separate best variable, as in the tree example, which sidesteps the question.

Integer overflow in the midpoint

int mid = (left + right) / 2;          // overflows when left + right > INT_MAX
int mid = left + (right - left) / 2;   // safe

This is exactly the Java Arrays.binarySearch bug mentioned in the introduction: it only appeared with arrays of more than about a billion elements, which is why it went unnoticed for years. Python integers do not overflow, so (left + right) // 2 is fine there. In C++, the same overflow also bites in binary search on the answer, when the bounds are up to 10⁹ or 10¹⁸ — use long long for the bounds and for the value feasible() accumulates.

Binary searching unsorted or wrongly sorted data

Binary search on unsorted data does not raise an error; it returns a wrong answer. The same happens when the data is sorted by a different key or order than the one you search with — sorted descending, sorted as strings ("10" < "9"), or sorted case-sensitively and searched case-insensitively. When a binary search gives an impossible result, check the sort order first.

Floating-point search spaces

When the answer is a real number (a square root, a minimum time), left <= right with +1/-1 updates makes no sense. Run a fixed number of iterations instead:

def sqrt(x, iters=100):
    left, right = 0.0, max(1.0, x)
    for _ in range(iters):             # each iteration halves the error
        mid = (left + right) / 2
        if mid * mid < x:
            left = mid
        else:
            right = mid
    return left

print(round(sqrt(2), 10))   # 1.4142135624

A fixed count is more robust than a while right - left > 1e-9 loop, which can spin forever once the gap reaches floating-point resolution for large values. For x = 10¹², adjacent doubles near the answer 10⁶ are about 10⁻¹⁰ apart, but near 10¹⁸ they are over 100 apart, so an absolute epsilon either never triggers or is meaningless. A hundred halvings shrink any starting interval that fits in a double below its resolution, so the fixed-count loop always ends and is always as precise as the type allows. If a relative tolerance is required, compare right - left against eps * max(1, abs(left)) instead.

Checking an implementation against brute force

Binary search bugs hide in edge cases that hand-written tests often skip, so the most reliable way to trust an implementation is to compare it against a slow version that is obviously correct. For lower bound, the obvious version is a linear scan for the first index with arr[i] >= x; for binary search on the answer, it is trying every candidate from the lower bound upward.

import random

def lower_bound_slow(arr, x):
    return next((i for i, v in enumerate(arr) if v >= x), len(arr))

for _ in range(10_000):
    arr = sorted(random.choices(range(10), k=random.randint(0, 8)))
    x = random.randint(-1, 11)
    assert lower_bound(arr, x) == lower_bound_slow(arr, x), (arr, x)

Small value ranges (0 to 9) and short arrays (0 to 8 elements) are deliberate: they generate many duplicates, empty arrays, single elements and targets outside the range, which are exactly the cases that break binary searches. When the assertion fails, it prints the smallest failing input, which is usually enough to see which update is off by one. I use this kind of check before trusting any hand-written variant, particularly the “last true” searches, where the rounding direction of mid is easy to get backwards.

---

Which binary search template to use

Question	Condition searched	Template
Is x in the array?	arr[mid] == x, then left or right	inclusive, early return
First index with value >= x	arr[i] >= x	half-open, right = mid
First index with value > x	arr[i] > x	half-open, right = mid
How many equal x?	upper_bound - lower_bound	—
Smallest X that works	feasible(X) is monotonic F…T	right = mid, floor midpoint
Largest X that works	feasible(X) is monotonic T…F	left = mid with ceiling midpoint, or inclusive with best
Real-valued answer	same condition	fixed number of iterations

The underlying skill is the same in every row: identify the monotonic yes/no condition, decide what left and right mean, and make every update preserve that meaning. When a binary search fails, test it on an empty array, a single element, two elements, and targets smaller and larger than everything — those five cases catch nearly all of the bugs above.

---

Practice Problems

Classic and bounds

• LeetCode 704: Binary Search
• LeetCode 35: Search Insert Position (lower bound)
• LeetCode 34: Find First and Last Position of Element (lower and upper bound)
• LeetCode 278: First Bad Version (first true of a condition)

Modified search spaces

• LeetCode 33: Search in Rotated Sorted Array
• LeetCode 74: Search a 2D Matrix
• LeetCode 69: Sqrt(x)

Binary search on the answer

• LeetCode 875: Koko Eating Bananas
• LeetCode 1011: Capacity to Ship Packages Within D Days
• LeetCode 410: Split Array Largest Sum
• LeetCode 1870: Minimum Speed to Arrive on Time

Harder

• LeetCode 4: Median of Two Sorted Arrays

The “modified search spaces” problems test whether you can find the monotonic condition when the array itself is not simply sorted. In a rotated sorted array such as [4, 5, 6, 7, 0, 1, 2], the condition arr[i] <= arr[-1] is false for the first run and true for the second, so the rotation point is a first-true search; once you know it, each half is an ordinary sorted array. A 2D matrix whose rows are sorted and each row starts after the previous one ends is a single sorted array of length rows × cols indexed as (i // cols, i % cols). Seeing the problem as “which yes/no question flips exactly once?” is the skill that transfers to the harder problems in this list.

---

Related Posts

• Quick Sort, Merge Sort and Heap Sort
• Two Pointers: Turning O(n²) Pair Searches into O(n)
• BFS vs DFS: Choosing a Graph Traversal
• Time Complexity Optimization Checklist