First and Last Position, Lower and Upper Bound, and bisect
20 min · Intermediate
Need help? Ask a tutor on WhatsApp (opens in a new tab)A stock list can hold the same level many times. The classic loop returns some match, but reports ask for the first one, the last one, or how many. Searching for the edge of the run solves all three.
Duplicates break the exact match
The lower bound is the first position whose value is at least the target. The upper bound is the first position whose value is greater than the target. Both are positions in 0..len(items).
With repeated values the classic loop returns any one match. Instead of searching for the value, search for a boundary: the first place where the values reach the target, or pass it.
Example 1 · Brute force: collect every position
stock = [5, 10, 10, 10, 20, 30]level = 10positions = [i for i, value in enumerate(stock) if value == level]print(positions[0], positions[-1], len(positions))1 3 3
What this code does
- This reads every item, so it is O(n) even though the list is sorted.
- It is correct and simple, and it is the answer to compare the faster versions with.
Lower bound by hand
Search the half-open window lo..hi, where hi starts one past the end. If items[mid] is too small, move lo past it. Otherwise mid could be the answer, so keep it with hi = mid.
def lower_bound(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
print(lower_bound([10, 20, 20, 20, 30], 20))1
Example 2 · Lower bound on four targets
def lower_bound(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
stock = [10, 20, 20, 20, 30]for target in [5, 20, 25, 99]: print(target, "->", lower_bound(stock, target))5 -> 0 20 -> 1 25 -> 4 99 -> 5
What this code does
- 5 is smaller than everything, so it would go at position 0. 20 starts at position 1.
- 25 would go at position 4, between 20 and 30. 99 is larger than everything, so the answer is 5, the length.
The answer can be len(items) when every value is smaller, which is why hi starts there. The loop ends when lo meets hi, and that position is the lower bound.
Upper bound, first, last and count
Upper bound is the same loop with <= in the test, so equal values are skipped too. Then the last position is upper bound minus one, and the count is upper minus lower.
def upper_bound(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
print(upper_bound([10, 20, 20, 20, 30], 20))4
Example 3 · First position, last position and count
def lower_bound(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
def upper_bound(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
def first_last(items, target): first = lower_bound(items, target) if first == len(items) or items[first] != target: return -1, -1 return first, upper_bound(items, target) - 1
stock = [5, 10, 10, 10, 20, 30]print(first_last(stock, 10))print(first_last(stock, 15))print(upper_bound(stock, 10) - lower_bound(stock, 10))(1, 3) (-1, -1) 3
What this code does
- Two O(log n) searches replace the O(n) scan, even when every item equals the target.
- The check
items[first] != targetcatches a missing value, because the lower bound of a missing value points at a different item.
Check that the target is really there before trusting the positions: the lower bound only says where it would go.
bisect does it for you
bisect_left is the lower bound and bisect_right is the upper bound. Both need a sorted list. Since Python 3.10 they also accept key=, so records can be searched without a second list.
from bisect import bisect_left, bisect_right
stock = [5, 10, 10, 10, 20, 30]print(bisect_left(stock, 10))print(bisect_right(stock, 10))print(bisect_right(stock, 10) - bisect_left(stock, 10))1 4 3
Example 4 · Count the values inside a range
from bisect import bisect_left, bisect_right
amounts = [40, 120, 120, 250, 400, 650, 900]low, high = 120, 650inside = bisect_right(amounts, high) - bisect_left(amounts, low)print(inside)5
What this code does
- bisect_left(low) is where the range starts and bisect_right(high) is where it ends, both included.
- The difference counts the items in 120..650 in O(log n), with no loop over the data.
Example 5 · Floor and ceiling of a budget
from bisect import bisect_left, bisect_right
prices = [120, 250, 400, 650, 900]budget = 500spot = bisect_right(prices, budget)print("best price within budget:", prices[spot - 1] if spot else None)spot = bisect_left(prices, budget)print("cheapest price at or above:", prices[spot] if spot < len(prices) else None)best price within budget: 400 cheapest price at or above: 650
What this code does
- The item just before bisect_right is the largest value that is not above the budget (the floor).
- The item at bisect_left is the smallest value that is not below it (the ceiling). Both can be missing, so check the edges.
Example 6 · Search records with key=
from bisect import bisect_left
orders = [("A17", 120), ("B02", 250), ("C45", 250), ("D09", 400)]first_big = bisect_left(orders, 250, key=lambda order: order[1])print(first_big, orders[first_big])1 ('B02', 250)What this code does
- The key function is applied to the list items, not to the target, so the records must already be sorted by that key.
- This needs Python 3.10 or newer. On older versions, search a separate list of keys instead.
Example 7 · Keep a list sorted with insort
from bisect import insort
log = [10, 20, 40]insort(log, 30)insort(log, 20)print(log)[10, 20, 20, 30, 40]
What this code does
- insort finds the place with binary search and inserts there, so the list stays sorted.
- The search is O(log n), but inserting shifts items, so each insert is O(n) overall.
These two calls give the first position after the run starts and the position after it ends. Their difference is the count of 10s.
Next step
Check your understanding
11 quick questions