Binary Search Time Bounds

EasyPython

Problem

Bloomberg time-series streams can contain repeated timestamps, such as multiple B-PIPE observations recorded at the same nanosecond. Given a sorted, nondecreasing array of integer timestamps and an inclusive time range, return the half-open index interval containing every timestamp in that range.

Implement time_range_bounds(timestamps, start, end) without using Python's bisect module.

Formal Specification

Input: timestamps, a list of integers sorted in nondecreasing order; start and end, integer timestamps with start <= end.
Output: a two-element list [left, right] where left is the first index with timestamps[left] >= start, and right is the first index with timestamps[right] > end. The matching observations are therefore timestamps[left:right].
If no timestamp falls within the range, return [k, k], where k is the insertion position for the range.

The algorithm must use binary search and run in O(log n) time. Do not scan the array linearly, including to skip duplicate timestamps.

Constraints

0 <= len(timestamps) <= 10^7
-10^18 <= timestamps[i], start, end <= 10^18
timestamps is sorted in nondecreasing order
start <= end

Function Signature

def time_range_bounds(timestamps, start, end):

Implement time_range_bounds(timestamps, start, end) without using Python's bisect module.

Formal Specification

Input: timestamps, a list of integers sorted in nondecreasing order; start and end, integer timestamps with start <= end.
Output: a two-element list [left, right] where left is the first index with timestamps[left] >= start, and right is the first index with timestamps[right] > end. The matching observations are therefore timestamps[left:right].
If no timestamp falls within the range, return [k, k], where k is the insertion position for the range.

The algorithm must use binary search and run in O(log n) time. Do not scan the array linearly, including to skip duplicate timestamps.