Equal range search and sliding-window top K

arr is sorted in non-decreasing order. Write equal_range(arr, target) -> tuple[int, int] returning the half-open index range (lo, hi) where arr[lo:hi] is exactly the run of elements equal to target. If target is absent, lo == hi and it is the index where target would be inserted.

The catch: elements can be any ordered type (ints, floats, strings, or your own objects), and you may compare them only with <. Two values count as equal when neither is < the other. That rules out the integer trick "search for target + 1", because floats and strings have no next value. bisect happens to work with < alone, but write the binary search yourself: that's the exercise.

It must use O(log n) comparisons. The tests pass a sequence that counts how often you read it.

equal_range([1, 2, 2, 2, 5], 2)        # (1, 4)
equal_range([1, 2, 2, 2, 5], 3)        # (4, 4)
equal_range(["ant", "bee", "bee"], "bee")  # (1, 3)
equal_range([], 7)                     # (0, 0)

Discussion (not tested)

• If a library gave you only lower_bound, when could you still get the right end of the range? What property of the element type does that need?
• Define precisely what each of lower_bound and upper_bound returns for duplicates, a missing value, and an empty array.