Binary Search & Its Variants

Binary search finds an item in a sorted list by checking the middle and throwing away the half that cannot contain the answer. Each step halves the search space, so even a list of 100 crore items needs only about 30 steps. It is simple to describe and famously easy to get slightly wrong.

In this lesson you will write binary search carefully using a loop invariant, adapt it to find the first and last position of a value, use Python's bisect module, and learn the most powerful variant: binary search on the answer to an optimisation problem.

The classic version

Keep two indexes, low and high, that mark the part of the list where the target can still be. The rule you keep true on every loop (the invariant) is: if the target is in the list, it is between low and high, inclusive.

def binary_search(items, target):
    low, high = 0, len(items) - 1
    while low <= high:                   # the range is not empty
        mid = (low + high) // 2
        print(f"  check index {mid} (value {items[mid]})")
        if items[mid] == target:
            return mid
        if items[mid] < target:
            low = mid + 1                # target is right of mid
        else:
            high = mid - 1               # target is left of mid
    return -1

train_numbers = [12002, 12015, 12301, 12417, 12559, 12801, 12951, 22691]
print("found at", binary_search(train_numbers, 12801))
print("found at", binary_search(train_numbers, 12000))

  check index 3 (value 12417)
  check index 5 (value 12801)
found at 5
  check index 3 (value 12417)
  check index 1 (value 12015)
  check index 0 (value 12002)
found at -1

Three details make it correct. The loop runs while low <= high, because a range with one item still needs checking. After checking mid, it moves past it with mid + 1 or mid - 1, so the range always shrinks. And the answer when the range becomes empty is "not found". Each step halves the range, so the time is O(log n) and the extra space is O(1).

First and last occurrence

When the list has duplicates, the classic version returns some matching index, not necessarily the first. Many questions need the first position where a value appears (or would be inserted), which is called the lower bound. Change the loop to search for a boundary instead of a match: the range is [low, high), and the answer is where low and high meet.

def lower_bound(items, target):
    """First index whose value is >= target."""
    low, high = 0, len(items)
    while low < high:
        mid = (low + high) // 2
        if items[mid] < target:
            low = mid + 1
        else:
            high = mid
    return low

def upper_bound(items, target):
    """First index whose value is > target."""
    low, high = 0, len(items)
    while low < high:
        mid = (low + high) // 2
        if items[mid] <= target:
            low = mid + 1
        else:
            high = mid
    return low

scores = [35, 42, 42, 42, 58, 61, 61, 90]
first, after_last = lower_bound(scores, 42), upper_bound(scores, 42)
print("first 42 at", first, "| last 42 at", after_last - 1, "| count", after_last - first)
print("where would 50 go?", lower_bound(scores, 50))
print("count of 70:", upper_bound(scores, 70) - lower_bound(scores, 70))

first 42 at 1 | last 42 at 3 | count 3
where would 50 go? 4
count of 70: 0

Notice the differences from the classic version: high starts at len(items) (one past the end), the loop uses <, and high = mid keeps mid in the range because it might be the answer. The only difference between the two functions is < against <=. Counting a value is just upper bound minus lower bound, in O(log n).

The bisect module

Python's standard library already has these two functions: bisect.bisect_left() is the lower bound and bisect.bisect_right() (also called bisect.bisect()) is the upper bound. bisect.insort() inserts an item while keeping the list sorted. Since Python 3.10, they also accept a key= function.

import bisect

# Departure times from Pune to Mumbai, as "HH:MM" strings (they sort correctly)
departures = ["05:50", "06:35", "07:15", "09:40", "12:10", "15:15", "17:45", "21:30"]

def next_train(now):
    i = bisect.bisect_left(departures, now)
    return departures[i] if i < len(departures) else "no more trains today"

print(next_train("07:15"))
print(next_train("10:05"))
print(next_train("22:00"))

bisect.insort(departures, "19:05")         # a new train is added
print(departures)

07:15
12:10
no more trains today
['05:50', '06:35', '07:15', '09:40', '12:10', '15:15', '17:45', '19:05', '21:30']

Finding the position with bisect is O(log n), but insort() still has to shift items to make room, so inserting is O(n) like list.insert().

Binary search on the answer

The most powerful use of binary search is not on a list at all. Many problems ask for the smallest (or largest) value that satisfies a condition, where the condition is monotonic: once it becomes true, it stays true for all bigger values. Then you can binary search over the possible answers, testing the condition at each mid.

Rohan wants to save a fixed amount every month for 36 months to reach ₹5,00,000. Assume his savings earn 1% interest per month (an example rate, not a real scheme). What is the smallest whole-rupee monthly amount that reaches the goal? Saving more never ends with less money, so the condition "reaches the goal" is monotonic.

def final_amount(monthly, months=36, rate=0.01):
    total = 0.0
    for _ in range(months):
        total = total * (1 + rate) + monthly
    return total

def smallest_monthly(goal):
    low, high = 1, goal                    # the answer is somewhere in here
    checks = 0
    while low < high:
        mid = (low + high) // 2
        checks += 1
        if final_amount(mid) >= goal:
            high = mid                     # mid works; maybe something smaller does
        else:
            low = mid + 1                  # mid is too small
    return low, checks

answer, checks = smallest_monthly(500_000)
print(f"Save Rs {answer} per month (found in {checks} checks)")
print(round(final_amount(answer)), round(final_amount(answer - 1)))

Save Rs 11608 per month (found in 19 checks)
500036 499993

The search tried only 19 of the 5 lakh possible amounts. The last line proves the answer: ₹11,608 a month reaches the goal and ₹11,607 does not. The same shape solves "minimum speed to finish in time", "largest batch size that fits in memory" and many interview problems: identify the range of possible answers, write a yes/no check, and make sure the check is monotonic.

Common mistakes

• Searching an unsorted list. Binary search gives wrong answers silently. Sort first, or use a set for membership.
• Infinite loops. If the range can stay the same size (for example low = mid when high = low + 1), the loop never ends. Make sure every branch shrinks the range.
• Mixing styles. Use either [low, high] with <= and mid ± 1, or [low, high) with < and high = mid. Mixing them causes off-by-one errors.
• A non-monotonic condition in binary search on the answer. If "works" can switch back to "does not work", binary search cannot be used.

Key points

• Binary search halves a sorted search space each step: O(log n) time, O(1) space.
• Keep an invariant about where the answer can be, and make every step shrink the range.
• Lower bound finds the first index with value ≥ target; upper bound finds the first index with value > target.
• bisect_left(), bisect_right() and insort() implement these in Python; they accept key= since Python 3.10.
• Binary search on the answer finds the smallest value that passes a monotonic yes/no check.

import bisect

def count_between(scores, low, high):
    return bisect.bisect_right(scores, high) - bisect.bisect_left(scores, low)

scores = [21, 34, 34, 45, 52, 52, 52, 67, 71, 88, 95]
print(count_between(scores, 34, 52))
print(count_between(scores, 60, 100))
print(count_between(scores, 0, 20))

6
4
0