Lower Bound and Upper Bound
Implement bisect_left and bisect_right from scratch, then apply them to find first and last positions of a target value.
What Are Lower and Upper Bounds?
The lower bound of a target value in a sorted array is the index of the first element greater than or equal to the target (often called bisect_left). The upper bound is the index of the first element strictly greater than the target (bisect_right). Together they bracket every occurrence of the target and enable O(log n) range queries.
These two operations are the foundation of many interview problems: count occurrences, find range, insert position, and more.
arr = [1, 2, 2, 2, 3, 5]
# lower bound of 2 => index 1 (first element >= 2)
# upper bound of 2 => index 4 (first element > 2)
# occurrences of 2 => upper - lower = 4 - 1 = 3
print('lower bound of 2:', 1)
print('upper bound of 2:', 4)
print('count of 2:', 4 - 1)Implementing Lower Bound (bisect_left)
bisect_left(arr, x) returns the leftmost index i such that arr[i] >= x, or len(arr) if all elements are smaller. The implementation uses an exclusive upper boundary: hi = len(arr), loop condition lo < hi, and update hi = mid when arr[mid] >= x. This ensures the answer converges to the leftmost valid position.
def bisect_left(arr, x):
lo, hi = 0, len(arr)
while lo < hi:
mid = lo + (hi - lo) // 2
if arr[mid] < x:
lo = mid + 1
else:
hi = mid # arr[mid] >= x, so potential answer
return lo # lo == hi == insertion point
arr = [1, 2, 2, 2, 3, 5]
print(bisect_left(arr, 2)) # 1
print(bisect_left(arr, 0)) # 0 (before all)
print(bisect_left(arr, 6)) # 6 (after all)
print(bisect_left(arr, 3)) # 4