Binary search and timestamp boundaries

Establish the ordering contract

Binary search requires ordered data or a monotonic predicate. Logs merged from different processes are not automatically sorted; clocks, buffering, and delayed delivery can change their order. This exercise uses finite, nondecreasing integer timestamps in one agreed unit. Check those assumptions once when loading a dataset.

Use a half-open interval [start, end) so adjacent query windows do not double-count the boundary. A lower bound finds the first position whose value is at least the target, or the list length if none exists.

Keep one invariant

Save as time_search.py:

def lower_bound(values, target):
    lo, hi = 0, len(values)
    while lo < hi:
        mid = (lo + hi) // 2
        if values[mid] < target:
            lo = mid + 1
        else:
            hi = mid
    return lo


def interval_indices(values, start, end):
    if start > end:
        raise ValueError("start must not exceed end")
    return lower_bound(values, start), lower_bound(values, end)


times = [10, 10, 20, 35, 60]
left, right = interval_indices(times, 10, 35)
assert (left, right) == (0, 3)
assert times[left:right] == [10, 10, 20]
assert interval_indices([], 0, 1) == (0, 0)
assert interval_indices(times, 20, 20) == (2, 2)

At each step, positions before lo have values below the target and positions at or after hi have values at least the target. The candidate boundary remains between them. Each iteration shrinks the interval; when they meet, the boundary is known.

Two bounds take O(log n) query work on a random-access list and constant auxiliary space. Returning the slice itself adds O(m) work and space for m results. Sorting raw observations first costs additional work, and inserting into a Python list still moves elements; binary search does not make insertion logarithmic.

Hand-trace a boundary query

For target 35 in [10, 10, 20, 35, 60], start at lo=0, hi=5. The midpoint is 2 with value 20, so move lo to 3. The next midpoint is 4 with value 60, so move hi to 4. The next midpoint is 3 with value 35, so move hi to 3. Both pointers meet at index 3: the first value at least 35. The upper query boundary excludes the value at that index.

Run python3 time_search.py, then try target 70: its insertion position is 5, the list length. Empty data also returns its length, zero. For the unsorted list [20, 10], target 15 can return the end even though 20 is present. That counterexample shows why the precondition matters; repeatedly validating the entire list inside every query would change the query cost.

Checkpoint and revision

Compare lower_bound with bisect.bisect_left. Test repeated timestamps, values outside the range, empty data, and equal boundaries. Show an unsorted counterexample and explain why validation belongs at ingestion if many queries reuse the same list. To understand a database index, inspect that database’s implementation separately; this exercise only covers binary search over a list.

Checkpoint answer: an equal start/end gives an empty interval; repeated timestamps at the start are included, and those equal to the end are excluded. Preserve those exact endpoint rules when moving to the next time-window exercise, whose interval deliberately uses a different open end.

Sources

Python bisect and performance notes↗ and Python sorting guidance↗.