Upper Bound Binary Search

Implement the upper bound binary search to find the first index where the value exceeds a target.

binary-search arrays searching

Implement the function `upper_bound(arr, target)` that takes a sorted list `arr` and a target value `target`. It should return the index of the first element in `arr` that is strictly greater than `target`. If no such element exists, return the length of the list. The input list is sorted in non-decreasing order. The index returned is the first position where `arr[i] > target`. Do not use built-in functions like `bisect`.

Constraints

0 <= len(arr) <= 1000. Elements are integers or floats. Complexity should be O(log n) time, O(1) space.

Example

>>> upper_bound([1, 2, 2, 3, 4], 2)
3
>>> upper_bound([1, 2, 3], 4)
3
>>> upper_bound([5, 6], 3)
0
>>> upper_bound([], 10)
0

8 points ~12 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Think about maintaining two boundaries: a low index and a high index.

When middle element is less than or equal to target, move left boundary to middle + 1.

When middle element is greater than target, move right boundary to middle.

The loop ends when low == high, which is the answer.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.