🔎 Python Algorithm Lab — Lower & Upper Bounds 🐍
Posted on: November 12, 2026
Description:
A binary search can find a match without finding the entire run of duplicates. Boundary searches answer a different question: where do matching values begin, and where do they stop?
Two boundaries, one range
For the sorted list [2, 4, 4, 4, 7, 9] and target 4:
- Lower bound = 1: the first position whose value is at least
4. - Upper bound = 4: the first position whose value is greater than
4. - Matches occupy
[1, 4): indices 1, 2 and 3. - Count:
4 - 1 = 3.
The upper bound is a position after the matches. It is not the last matching index.
Equality decides the direction
def lower_bound(a, target):
lo, hi = 0, len(a)
while lo < hi:
mid = (lo + hi) // 2
if a[mid] < target:
lo = mid + 1
else:
hi = mid
return lo
For upper bound, use a[mid] <= target instead. Equality now moves lo past the midpoint rather than moving hi toward it.
The half-open unclassified interval is [lo, hi). Each iteration makes it smaller. When its endpoints meet, the boundary has been found. The input must be sorted in ascending order and remain unchanged during the search.
Follow the actual search
| Search | Midpoint indices | Final boundary |
|---|---|---|
| Lower bound for 4 | 3 → 1 → 0 | 1 |
| Upper bound for 4 | 3 → 5 → 4 | 4 |
The notebook verifies 1,260 array/target cases against Python’s standard library, checks both partitions and the match count, and checks that every traced interval shrinks. These are correctness checks, not timing benchmarks.
Missing values still have positions
Searching for 5 returns (4, 4): an empty matching range and count zero. Searching for 10 returns (6, 6), the position after the list. An empty list returns (0, 0).
Do not blindly access a[lower]: the returned position can equal len(a). To obtain the last match as upper - 1, first check that lower < upper.
Use Python’s built-in tools
from bisect import bisect_left, bisect_right
values = [2, 4, 4, 4, 7, 9]
left = bisect_left(values, 4)
right = bisect_right(values, 4)
count = right - left # 3
bisect_left and bisect_right return insertion positions before and after existing equal values. See the official Python documentation.
Each search takes O(log n) time with constant-time indexing and comparisons. The implementations use O(1) auxiliary space. Counting by subtraction adds constant work; copying a slice of k matches costs O(k). Sorting and list insertion have separate costs. Notebook tracing and its validation scans are test instrumentation, not part of the search complexity.
Takeaway: find the first allowed position on each side, then treat the matches as [lower, upper).
No comments yet. Be the first to comment!