Binary Search Patterns
Plain binary search is easy to explain and surprisingly easy to get wrong. People who know the idea still lose an hour to a loop that never ends, or one that misses the last item. This lesson fixes that with one habit: say what is always true, then write the loop to keep it true. The same habit then solves a whole family of problems, including some where there is no list at all. You need the plain version first, which Algorithms Basics teaches.
Learning Objectives
After this lesson, you will be able to:
- State the invariant of a binary search loop in one sentence, and use it to decide every line of the loop
- Write both loop shapes, closed [lo, hi] and half-open [lo, hi), and say when to pick each
- Find the first and last position of a value with lower bound and upper bound, and match them to bisect_left and bisect_right, including key=
- Search a sorted list that was rotated, and say why duplicates break the fast version
- Search on the answer: spot a yes or no test that flips once, and use it to find the smallest capacity, an integer square root, or the smallest x where f(x) is true
- Search real numbers with a fixed number of rounds, find a peak without sorted data, and state the time and space of each pattern
Prerequisites
Before You Start
#The Idea in Five Lines
Big-O and searching built binary search. Here is the whole idea again, so this lesson stands on its own.
- The list must be sorted, smallest first.
- Look at the middle item.
- If it is too small, the target can only be to its right. If it is too big, only to its left.
- Throw away the half that cannot hold the target, and repeat on the other half.
- Each look halves what is left, so a million items need about 20 looks. That is O(log n).
Everything below is about doing step 4 without a mistake, and about using the same idea when the "list" is a range of possible answers.
Some words first. A sorted list has its values in order from smallest to largest. An index is a position, starting at 0. A probe is one look at the middle item. The names
lo and hi are two indexes that mark the part of the list still in play. Items in that part are called candidates, because the answer might still be one of them.#The Invariant: What Is Always True
An invariant is a sentence about your variables that is true before the loop starts, true after every pass, and still true when the loop stops. It is the loop's promise. If the promise holds at the start, and every pass keeps it, then the last state of the loop tells you the answer.
For the first loop shape, the promise is this: if the target is in the list, it is at an index from
lo to hi, both ends included. We call that range closed, because both ends belong to it. Everything left of lo is too small, and everything right of hi is too big.pythonrunnable cell
def trace_closed(items, target):
"""Closed shape with a check of the invariant on every pass."""
lo, hi = 0, len(items) - 1
while lo <= hi:
# Invariant: every value left of lo is smaller, every value right of hi is bigger.
assert all(v < target for v in items[:lo])
assert all(v > target for v in items[hi + 1:])
mid = (lo + hi) // 2
print(f"lo={lo} hi={hi} mid={mid} items[mid]={items[mid]}")
if items[mid] == target:
return mid
if items[mid] < target:
lo = mid + 1
else:
hi = mid - 1
print(f"lo={lo} hi={hi} (lo is past hi: nothing left)")
return -1
items = [3, 8, 12, 17, 21, 26, 30]
print(trace_closed(items, 10))Before you read the output, work it by hand. The target 10 is not in the list.
What Do You Think?
The list is [3, 8, 12, 17, 21, 26, 30] and the target is 10. The first probe is at index 3, which holds 17. When the loop stops, what are lo and hi?
Here is the same run as a table, one row per pass.
| Pass | lo | hi | mid | Item at mid | What the invariant lets us say |
|---|---|---|---|---|---|
| 1 | 0 | 6 | 3 | 17 | 17 is bigger than 10, so indexes 3 to 6 are out: hi = 2 |
| 2 | 0 | 2 | 1 | 8 | 8 is smaller than 10, so indexes 0 to 1 are out: lo = 2 |
| 3 | 2 | 2 | 2 | 12 | 12 is bigger than 10, so index 2 is out: hi = 1 |
| end | 2 | 1 | the range is empty, so 10 is not in the list |
Two facts fall out of the table. The loop must stop, because every pass either returns or moves
lo up or hi down by at least one. And when it stops with lo past hi, the closed range is empty, so the target is not there. Look at where lo ended up: 2. That is exactly where 10 would be inserted to keep the list sorted. We use that soon.The next picture runs the same loop on 16 numbers. Pick 23 first, then pick 77, which is not in the list. Watch
left and right close in. When the target is missing, they cross, and left lands on the insertion point, the place where 77 would go.Binary Search: Watch the Invariant HoldInteractive
Pick a target and step through. At every step, everything outside the bright range has been ruled out. Try 77 and watch the two ends cross.
Loading visualization...
#Two Loop Shapes: Closed and Half-Open
The closed shape above is natural for the question "is the target here, and where?" The second shape suits the question "where is the boundary?" It is called half-open: the range
[lo, hi) includes lo but not hi. The square bracket means included, and the round bracket means left out. Python slices work the same way: items[2:5] includes index 2 and leaves out index 5.pythonrunnable cell
def find_closed(items, target):
lo, hi = 0, len(items) - 1 # closed [lo, hi]: both ends are candidates
while lo <= hi:
mid = (lo + hi) // 2
if items[mid] == target:
return mid
if items[mid] < target:
lo = mid + 1 # items[mid] is ruled out, so skip past it
else:
hi = mid - 1
return -1
def insertion_point(items, target):
lo, hi = 0, len(items) # half-open [lo, hi): hi is NOT a candidate
while lo < hi:
mid = (lo + hi) // 2
if items[mid] < target:
lo = mid + 1
else:
hi = mid # items[mid] might still be the answer, keep it
return lo
items = [3, 8, 12, 17, 21, 26, 30]
print(find_closed(items, 21), insertion_point(items, 21))
print(find_closed(items, 10), insertion_point(items, 10))
print(insertion_point(items, 99), insertion_point(items, 1))
# Output:
# 4 4
# -1 2
# 7 0The two shapes differ in four places. Compare them side by side.
Closed [lo, hi] | Half-open [lo, hi) | |
|---|---|---|
| Start | hi = len(items) - 1 | hi = len(items) |
| Keep looping while | lo <= hi | lo < hi |
Rule mid out | lo = mid + 1 or hi = mid - 1 | lo = mid + 1 |
Keep mid as a candidate | not needed | hi = mid |
| When it stops | lo is one past hi, range empty | lo equals hi, one spot left |
The half-open shape has a gift. When
mid might be the answer, you can keep it with hi = mid, and the range still shrinks, because hi is not part of the range. In the closed shape, writing lo = mid or hi = mid can stall. That is the cause of the most common infinite loop, and we meet it in Common Mistakes.The half-open shape also returns a position even when nothing matches, and that position is meaningful. For
insertion_point(items, 10) it returns 2: the first index whose item is 10 or more. So for most of this lesson we use half-open, and wrap it once in a tiny helper.pythonrunnable cell
def first_true(lo, hi, is_true):
"""Smallest i in [lo, hi) with is_true(i), or hi if there is none.
Needs is_true to be False for a while, then True for ever after."""
while lo < hi:
mid = (lo + hi) // 2
if is_true(mid):
hi = mid # mid might be the first True: keep it
else:
lo = mid + 1 # mid is False: everything up to mid is ruled out
return loThe invariant for
first_true is: everything left of lo is False, and everything from hi on is True (or is past the end). When lo meets hi, that meeting point is the first True. Almost every pattern below is one call to this function with a different yes or no test. Notice that it never mentions a list. It only asks a question about an index, so it works on any range of numbers.#Off-by-One Traps and How to Test for Them
An off-by-one error means a loop runs one time too many or too few, or a bound is one too big or too small. Binary search invites them because there are four small choices in a row. Use this checklist every time you write a loop.
First, write the invariant as a comment before you write any code. Second, choose the shape and let it set your starting
hi and your loop test, as in the table above. Third, for each branch, ask "is mid ruled out?" If yes, skip past it. If no, keep it, which needs the half-open shape. Fourth, check that the range shrinks on every pass, or the loop can run forever. Fifth, check what the answer means when the loop stops.In Python,
(lo + hi) // 2 cannot overflow, because integers grow as large as needed. In C and Java, write lo + (hi - lo) // 2 instead.The best defence is a brute-force check on tiny inputs. The cell below tries every sorted list of up to five values, each from 0 to 3, with every target from -1 to 4. It compares both functions with the plain meaning: a value is found if
in says so, and the insertion point is the count of smaller values.pythonrunnable cell
from itertools import product
def find_closed(items, target):
lo, hi = 0, len(items) - 1
while lo <= hi:
mid = (lo + hi) // 2
if items[mid] == target:
return mid
if items[mid] < target:
lo = mid + 1
else:
hi = mid - 1
return -1
def insertion_point(items, target):
lo, hi = 0, len(items)
while lo < hi:
mid = (lo + hi) // 2
if items[mid] < target:
lo = mid + 1
else:
hi = mid
return lo
cases = 0
for size in range(0, 6): # lists of length 0 to 5
for items in product(range(4), repeat=size): # values 0..3, repeats allowed
if list(items) != sorted(items):
continue
for target in range(-1, 5):
found = find_closed(items, target)
assert (found == -1) == (target not in items)
assert found == -1 or items[found] == target
want = sum(1 for v in items if v < target) # how many values are smaller
assert insertion_point(items, target) == want
cases += 1
print(cases, "cases agree")
# Output:
# 756 cases agreeLists of length 0, 1 and 2 are where most slips show up, and this check covers them all.
#Lower Bound and Upper Bound
A sorted list can hold repeated values, such as
[1, 2, 2, 2, 3, 5]. Two questions come up all the time: where does the run of 2s start, and where does it end? Two names answer them.The lower bound of x is the first index whose item is x or more. The upper bound of x is the first index whose item is bigger than x. If x is in the list, the run of x's fills the indexes from the lower bound up to, but not including, the upper bound. Python's
bisect_left is the lower bound and bisect_right is the upper bound.What Do You Think?
For items = [1, 2, 2, 2, 3, 5], what do bisect_left(items, 2) and bisect_right(items, 2) return?
Trace both by hand with the half-open shape. For the lower bound the test at
mid is "item is 2 or more". For the upper bound it is "item is more than 2". The list has six items, so we start with lo = 0 and hi = 6.| Search | lo | hi | mid | Item at mid | Test | Move |
|---|---|---|---|---|---|---|
| lower bound of 2 | 0 | 6 | 3 | 2 | 2 or more: yes | hi = 3 |
| 0 | 3 | 1 | 2 | yes | hi = 1 | |
| 0 | 1 | 0 | 1 | no | lo = 1 | |
| 1 | 1 | stop | answer 1 | |||
| upper bound of 2 | 0 | 6 | 3 | 2 | more than 2: no | lo = 4 |
| 4 | 6 | 5 | 5 | yes | hi = 5 | |
| 4 | 5 | 4 | 3 | yes | hi = 4 | |
| 4 | 4 | stop | answer 4 |
The code is two calls to
first_true. We check it against bisect for every x from -1 to 7.pythonrunnable cell
import bisect
def first_true(lo, hi, is_true):
while lo < hi:
mid = (lo + hi) // 2
if is_true(mid):
hi = mid
else:
lo = mid + 1
return lo
def lower_bound(items, x):
return first_true(0, len(items), lambda i: items[i] >= x)
def upper_bound(items, x):
return first_true(0, len(items), lambda i: items[i] > x)
def first_and_last(items, x):
i = lower_bound(items, x)
if i == len(items) or items[i] != x: # the check that x is really there
return (-1, -1)
return (i, upper_bound(items, x) - 1)
items = [1, 2, 2, 2, 3, 5]
print(lower_bound(items, 2), upper_bound(items, 2))
print(lower_bound(items, 4), upper_bound(items, 4))
print("count of 2:", upper_bound(items, 2) - lower_bound(items, 2))
print(first_and_last(items, 2), first_and_last(items, 4))
for x in range(-1, 8):
assert lower_bound(items, x) == bisect.bisect_left(items, x)
assert upper_bound(items, x) == bisect.bisect_right(items, x)
print("agrees with bisect")
# Output:
# 1 4
# 5 5
# count of 2: 3
# (1, 3) (-1, -1)
# agrees with bisectLook at the missing value 4. Both bounds are 5, so the run has length 0, and 5 is where 4 would be inserted. The lower bound alone does not tell you that x is present, because it returns a position even for a missing value. That is why
first_and_last checks items[i] != x before it trusts the answer. Also check i == len(items) first, or the next line reads past the end.Two more uses follow. The number of items from a low to a high value, both included, is
bisect_right(items, high) - bisect_left(items, low). And the place to insert x is the lower bound, or the upper bound to go after the old copies of x.#bisect and the key Argument
Python's
bisect module does this for you, and since Python 3.10 it accepts key=, a function that turns each list item into the value to compare. That is how you search a list of records sorted by one field.pythonrunnable cell
import bisect
people = [("Ana", 20), ("Bo", 25), ("Cy", 25), ("Di", 31)] # sorted by age
first = bisect.bisect_left(people, 25, key=lambda p: p[1])
after = bisect.bisect_right(people, 25, key=lambda p: p[1])
print(first, after)
print(people[first:after])
scores = [55, 62, 70, 70, 85, 91]
print(bisect.bisect_left(scores, 70), bisect.bisect_right(scores, 70))
low, high = 62, 85
print(bisect.bisect_right(scores, high) - bisect.bisect_left(scores, low))
# key is applied to the list items, never to the value you search for
try:
bisect.bisect_left(people, ("Bo", 25), key=lambda p: p[1])
except TypeError as error:
print("TypeError:", error)
# Output:
# 1 3
# [('Bo', 25), ('Cy', 25)]
# 2 4
# 4
# TypeError: '<' not supported between instances of 'int' and 'tuple'Read the last case slowly. The
key function is applied to the items of the list, not to the value you are looking for. So you pass the already-extracted age, 25, and not the whole record. Passing the record makes Python compare a number with a tuple, which fails. The list must also be sorted by the same key. Sorting by name and searching by age gives meaningless answers and no error.Finding the place is O(log n), but
bisect.insort still costs O(n) overall, because inserting into a list shifts every item after the spot. If you need many inserts into a sorted collection, the trees lesson and the heap lesson show better structures.#Search in a Rotated Sorted List
A list is rotated when a sorted list has had a front piece moved to the back, such as
[15, 18, 22, 3, 5, 8, 11], which is [3, 5, 8, 11, 15, 18, 22] with the first four moved to the end. The place where the values drop, from 22 to 3, is the pivot. The pivot index holds the smallest value.Plain binary search fails here. If the middle item is too small, the target might be to the right, or it might be to the left past the pivot. The trick is to turn the problem into two easy ones. First find the pivot. Then search as if the list were sorted, by mapping each virtual position
v to the real index (v + pivot) % n.Finding the pivot needs a yes or no test that flips once. Compare each item with the last item. Items in the first piece are all bigger than the last item, and items in the second piece are all smaller or equal. So "item is at most the last item" is False, False, False, True, True, True, True. That is exactly the shape
first_true wants. Here is the hand trace on [15, 18, 22, 3, 5, 8, 11], where the last item is 11.| lo | hi | mid | Item at mid | At most 11? | Move |
|---|---|---|---|---|---|
| 0 | 7 | 3 | 3 | yes | hi = 3 |
| 0 | 3 | 1 | 18 | no | lo = 2 |
| 2 | 3 | 2 | 22 | no | lo = 3 |
| 3 | 3 | stop | pivot is 3 |
pythonrunnable cell
def first_true(lo, hi, is_true):
while lo < hi:
mid = (lo + hi) // 2
if is_true(mid):
hi = mid
else:
lo = mid + 1
return lo
def find_pivot(items):
"""Index of the smallest value in a rotated sorted list of distinct values."""
last = items[-1]
return first_true(0, len(items), lambda i: items[i] <= last)
def search_rotated(items, target):
n = len(items)
if n == 0:
return -1
pivot = find_pivot(items)
# Pretend the list is sorted: virtual position v lives at real index (v + pivot) % n.
v = first_true(0, n, lambda v: items[(v + pivot) % n] >= target)
if v < n and items[(v + pivot) % n] == target:
return (v + pivot) % n
return -1
rotated = [15, 18, 22, 3, 5, 8, 11]
print(find_pivot(rotated))
print(search_rotated(rotated, 5), search_rotated(rotated, 22), search_rotated(rotated, 4))
print(find_pivot([3, 5, 8, 11]), search_rotated([3, 5, 8, 11], 11)) # not rotated at all
print(search_rotated([7], 7), search_rotated([], 7))
# duplicates break the yes or no test
print(find_pivot([2, 2, 2, 0, 2]))
# Output:
# 3
# 4 2 -1
# 0 3
# 0 -1
# 0The last line is the warning. In
[2, 2, 2, 0, 2] every item is at most the last item, so the test is True everywhere and the pivot comes out as 0, but the smallest value sits at index 3. With repeated values the left half and the right half can look alike, and binary search can no longer tell which half to drop. The usual repair shrinks the range one step at a time when the middle equals the last item. It works, but in the worst case it costs O(n). Use the version above only when the values are distinct.#Search on the Answer
So far we searched a list. Now there is no list. We have a question of the form "what is the smallest number x that works?", and a way to check any single x with a yes or no answer. The idea is to binary search the range of possible answers, and use the check as the comparison.
A yes or no test is called a predicate. Binary search on the answer needs the predicate to be monotone: once it turns True, it stays True for every bigger x. Or the other way round, True and then False. It flips at most once. The monotone test is a question you ask yourself before writing any code:
If x works, must x + 1 also work? If yes, the predicate is monotone and you can search for the smallest x that works. If you can name even one pair where the answer breaks, do not use binary search.
Here is the standard example. A depot must ship packages in the given order, in at most D days. Each day a truck carries as many of the next packages as fit under its weight capacity. What is the smallest capacity that gets everything out in time?
Try the test. If capacity 6 is enough, is capacity 7? Yes: a bigger truck can do the same trips. So the predicate "can ship with capacity c" is False for small c and True from some c onward. The answer is the first True. The search range is from the heaviest single package (a truck must carry it) up to the total weight (one day is enough).
Take weights
[3, 2, 2, 4, 1, 4] and 3 days. With capacity 5, the trips are [3, 2], [2], [4, 1], [4]: four days, too many. With capacity 6, the trips are [3, 2], [2, 4], [1, 4]: three days, enough. The range is 4 to 16, and the half-open search probes 10, 7, 5 and 6.| lo | hi | mid | Can ship in 3 days? | Move |
|---|---|---|---|---|
| 4 | 17 | 10 | yes | hi = 10 |
| 4 | 10 | 7 | yes | hi = 7 |
| 4 | 7 | 5 | no | lo = 6 |
| 6 | 7 | 6 | yes | hi = 6 |
| 6 | 6 | answer is 6 |
pythonrunnable cell
def first_true(lo, hi, is_true):
while lo < hi:
mid = (lo + hi) // 2
if is_true(mid):
hi = mid
else:
lo = mid + 1
return lo
def can_ship(weights, days, capacity):
"""Can the packages, in order, go in this many days with this capacity?"""
used, load = 1, 0
for w in weights:
if load + w > capacity:
used += 1
load = 0
load += w
return used <= days
def min_capacity(weights, days):
lo, hi = max(weights), sum(weights) + 1 # half-open: sum(weights) always works
return first_true(lo, hi, lambda c: can_ship(weights, days, c))
weights = [3, 2, 2, 4, 1, 4]
for c in range(3, 8):
print(c, can_ship(weights, 3, c))
print(min_capacity(weights, 3))
print(min_capacity([1, 2, 3, 4, 5, 6, 7, 8, 9, 10], 5))
# Output:
# 3 False
# 4 False
# 5 False
# 6 True
# 7 True
# 6
# 15The same shape solves many problems. Only two parts change: the range, and the predicate. Before the next example, try a quick test of your eye.
What Do You Think?
Which of these yes or no questions about a whole number x (from 0 up) flips from False to True once and stays True, so you could binary search it?
The first question in that list is the integer square root. The integer square root of n is the biggest whole number x with
x * x <= n. We find the first x where x * x > n and step back one. A search for the largest x that passes a test is always "first x that fails, minus one".pythonrunnable cell
import math
def first_true(lo, hi, is_true):
while lo < hi:
mid = (lo + hi) // 2
if is_true(mid):
hi = mid
else:
lo = mid + 1
return lo
def integer_sqrt(n):
"""Largest x with x * x <= n."""
return first_true(0, n + 2, lambda x: x * x > n) - 1
def looks_monotone(is_true, lo, hi):
"""Brute-force check on a small range: no False may come after a True."""
seen_true = False
for x in range(lo, hi):
if is_true(x):
seen_true = True
elif seen_true:
return False
return True
print([integer_sqrt(n) for n in (0, 1, 2, 15, 16, 17)])
print(integer_sqrt(10**12), integer_sqrt(10**12 - 1))
assert all(integer_sqrt(n) == math.isqrt(n) for n in range(5000))
print("matches math.isqrt")
print(looks_monotone(lambda x: x * x > 50, 0, 100))
print(looks_monotone(lambda x: x % 7 == 0, 1, 100))
# Output:
# [0, 1, 1, 3, 4, 4]
# 1000000 999999
# matches math.isqrt
# True
# FalseThe helper
looks_monotone is a cheap safety net. When you are unsure whether a predicate flips once, run it on a small range first. It cannot prove monotone, but one False after a True proves it is not.Two habits make these problems routine. Choose
lo as the smallest answer that could possibly be right, and hi as one past an answer that surely works. Write the predicate as a separate small function and test it alone. In the shipping problem, hi is the total weight plus one, so that "everything on one truck" stays inside the half-open range.#Searching Real Numbers: Count Rounds, Not Tolerance
Sometimes the answer is a real number, such as the square root of 2. We cannot step by one, but we can still halve the interval. Each round replaces the interval with the half that holds the answer, and the gap shrinks to half its size.
The tempting loop stops when the interval is smaller than a tolerance, such as
hi - lo > 1e-9. It looks safe, and it has a trap. Floats have limited precision, and the gap between neighbouring floats grows with their size. Around 10 to the power 16, the next float after lo is 2 away. Then the middle of lo and hi rounds back to lo, nothing moves, and the interval never gets smaller than the gap. The loop runs forever.The safe habit is to run a fixed number of rounds. The width after k rounds is the starting width divided by 2 to the power k, so you can choose k from the precision you want. Sixty rounds cut any gap by about a billion billion.
pythonrunnable cell
import math
def float_sqrt(x, rounds=60):
"""Square root of x >= 0 by halving the interval a fixed number of times."""
lo, hi = 0.0, max(1.0, x) # sqrt(x) is always inside [0, max(1, x)]
for _ in range(rounds):
mid = (lo + hi) / 2
if mid * mid < x:
lo = mid # mid is too small
else:
hi = mid # mid is big enough
return (lo + hi) / 2
print(f"{float_sqrt(2):.12f}", f"{math.sqrt(2):.12f}")
print(f"{float_sqrt(0.25):.12f}", f"{float_sqrt(1e10):.6f}")
gap = 2.0 # the starting width for sqrt(2) is 2
for rounds in (1, 10, 20, 30, 50, 60):
print(rounds, f"{gap / 2 ** rounds:.3e}")
def sqrt_tolerance(x, tol=1e-9, cap=100000):
"""The tolerance version, with a cap so this demo cannot hang."""
lo, hi = 0.0, max(1.0, x)
loops = 0
while hi - lo > tol and loops < cap:
mid = (lo + hi) / 2
if mid * mid < x:
lo = mid
else:
hi = mid
loops += 1
return loops
print(sqrt_tolerance(2), sqrt_tolerance(1e30))
lo = 1e16
hi = lo + 2
print((lo + hi) / 2 == lo, (lo + hi) / 2 == hi)
# Output:
# 1.414213562373 1.414213562373
# 0.500000000000 100000.000000
# 1 1.000e+00
# 10 1.953e-03
# 20 1.907e-06
# 30 1.863e-09
# 50 1.776e-15
# 60 1.735e-18
# 31 100000
# True FalseThe tolerance loop finishes in 31 rounds for the square root of 2, but for 1e30 it hits the cap of 100,000 and has still not converged. The last two lines show why: the middle of
1e16 and 1e16 + 2 equals lo, so lo can never move. A fixed round count has no such trap, because it simply stops. The cost is O(rounds) steps, each evaluating your test once.#Peak Element: Binary Search Without Sorting
A peak is a value bigger than both of its neighbours. The two ends count as having a neighbour of minus infinity, so the first item is a peak if it beats the second. The list is not sorted. Suppose adjacent values are never equal, and you want any peak, not the biggest one.
Binary search still works, because what it needs is not sorted data. It needs a rule that says which half is safe to throw away. Here the invariant is: a peak exists somewhere in
[lo, hi]. Look at mid and mid + 1. If items[mid] is smaller, the list is climbing, and a climb must end in a peak on the right, even if only at the last item. Otherwise items[mid] beats its right neighbour, and a peak is at mid or to the left.Trace
[1, 3, 5, 4, 2, 6, 1], which has peaks at index 2 (value 5) and index 5 (value 6).| lo | hi | mid | Compare | Move |
|---|---|---|---|---|
| 0 | 6 | 3 | 4 against 2: not smaller | hi = 3 |
| 0 | 3 | 1 | 3 against 5: smaller | lo = 2 |
| 2 | 3 | 2 | 5 against 4: not smaller | hi = 2 |
| 2 | 2 | peak at index 2 |
pythonrunnable cell
def find_peak(a):
"""Index of any peak: a value bigger than both neighbours (edges count as -infinity).
Needs a[i] != a[i + 1] for every i."""
lo, hi = 0, len(a) - 1 # closed: a peak is always inside a[lo..hi]
while lo < hi:
mid = (lo + hi) // 2
if a[mid] < a[mid + 1]:
lo = mid + 1 # going uphill to the right, so a peak is right of mid
else:
hi = mid # a[mid] > a[mid + 1], so a peak is at mid or to its left
return lo
a = [1, 3, 5, 4, 2, 6, 1]
print(find_peak(a), a[find_peak(a)])
print(find_peak([1, 2, 3, 4]), find_peak([4, 3, 2, 1]), find_peak([9]))
# Output:
# 2 5
# 3 0 0This loop keeps
mid with hi = mid, because mid might be the peak. That is safe here, since the loop runs only while lo < hi, so mid is always less than hi, and mid + 1 never passes the end. It takes O(log n) time and O(1) space. A one-item list, like the last case, never enters the loop and returns index 0.#How Fast Is Each One?
Every pattern throws away half of a range per probe, so the number of probes is about log base 2 of the range size. What changes is the cost of one probe.
| Pattern | Time | Space | Why |
|---|---|---|---|
| Find a value (closed loop) | O(log n) | O(1) | one comparison per probe, three variables |
| Lower bound, upper bound, bisect | O(log n) | O(1) | the same loop, a different test |
bisect.insort | O(n) | O(1) extra | finding the spot is O(log n), but inserting shifts items |
| Rotated list, distinct values | O(log n) | O(1) | two searches, each O(log n) |
| Rotated list, repeats allowed | O(n) worst case | O(1) | equal ends can force one-step shrinking |
| Search on the answer | O(log R times C) | O(1) | R is the size of the range, C the cost of one check |
| Shipping example | O(n log S) | O(1) | n packages checked per probe, S the total weight |
| Real numbers, fixed rounds | O(rounds times C) | O(1) | C is the cost of one test |
| Peak element | O(log n) | O(1) | one pair of neighbours per probe |
A recursive version that passes
lo and hi as arguments also takes O(log n) time, but it keeps one stack frame per level, so its space is O(log n). The loop versions above use O(1).#When Not to Use Binary Search
Binary search needs a rule for which half to drop. Without it, you are guessing.
If the data is not sorted and you search once, a plain scan is O(n) and sorting first costs O(n log n), so the scan wins. Sorting pays off when you search many times. If you only need to know "is x present?" and the order does not matter, a set answers in O(1) on average and needs no sorting. If the data changes often, keeping a list sorted costs O(n) per insert. For tiny lists of ten items or fewer, a scan is just as fast and simpler. Finally, if the yes or no test cannot be shown monotone, do not search on the answer. Use a different tool.
#Where It Shows Up
Binary search on the answer is a working method as well as a puzzle. The tool
git bisect finds the first bad version of a project: "is this version broken?" is False for old versions and True from the first bad one on, so it takes about log n test builds instead of n. Picking a score threshold for a model, such as the lowest threshold that keeps precision above a target, is the same search when precision only rises as the threshold rises. The largest batch size that fits in memory is another, if memory use only grows with batch size. In each case, check the monotone test first.NumPy has
numpy.searchsorted, which is lower bound and upper bound on arrays, with side="left" and side="right" matching bisect_left and bisect_right. Database indexes and sorted files rely on the same halving idea to find a row in a few probes.#Common Mistakes
#Try It
Work the ladder in order, and do not skip a rung. Each rung has a stub with a TODO and an Expected line to check yourself against. Rung 4 starts with a function that has two bugs, and rung 5 asks you to turn a slow search into binary search on the answer and to count the calls.
pythonplayground.py · Pyodide
Tests · Rung 1 prints '1 3 0'. Rung 2 prints '(1, 3) (-1, -1)'. Rung 3 prints '4 -1'. Rung 4 prints '[0, 1, 1, 3, 4, 4] 1000000'. Rung 5 prints '4089 3890' for the slow version and '4089 15' for the fast one.
Hints: in rung 1,
hi is len(items), not len(items) - 1, and a smaller item means lo = mid + 1. In rung 3, the second search is rung 1 run on the virtual list. In rung 4, ask what the loop finds when it stops, and whether that is the answer or one past it. In rung 5, the search range for the answer starts at the heaviest package.#Recap
Binary search is a loop that keeps a promise. The invariant says what is true about
lo and hi on every pass, and the code is whatever keeps it true. The closed shape [lo, hi] suits "is it here?" and loops while lo <= hi. The half-open shape [lo, hi) suits "where is the boundary?", starts with hi = len(items), loops while lo < hi, and can keep mid with hi = mid. Test every loop on lists of length 0, 1 and 2.Lower bound is the first index with an item of x or more, and upper bound is the first with an item bigger than x. They match
bisect_left and bisect_right, and key= applies to the list items only. A rotated list needs a pivot, found with the test "at most the last item". Search on the answer needs a predicate that flips once, and costs the number of probes times the cost of one check. Real numbers need a fixed round count. A peak needs only a rule for which half to drop. Every pattern is O(log n) probes, with O(1) space in loop form.Quick Check1 / 6
In a closed binary search loop (lo and hi both candidates), the item at mid is smaller than the target. Which update keeps the invariant and guarantees the range shrinks?
Recap
Key Takeaways
- Write the invariant first: the sentence about lo and hi that stays true before, during and after the loop
- Closed [lo, hi] loops while lo <= hi and rules mid out; half-open [lo, hi) loops while lo < hi and can keep mid with hi = mid
- Lower bound is the first index with an item of x or more, upper bound the first with an item bigger than x; they are bisect_left and bisect_right
- key= in bisect applies to the list items, so pass the extracted value, not the whole record
- Search on the answer when the test flips once: ask whether x working means x + 1 works
- Search real numbers with a fixed number of rounds, not a tolerance
- Binary search needs a safe rule for which half to drop, and sorted data is only one way to get it