AW Dev Rethought

✂️ Perfection is achieved not when there is nothing more to add, but when there is nothing left to take away - Antoine de Saint-Exupéry

🔎 Python Algorithm Lab — Lower & Upper Bounds 🐍


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).


Link copied!

Comments

Add Your Comment

Comment Added!