lower_bound found the first element that is at least target. upper_bound is its twin: it returns the index of the first element strictly greater than target. Together they bracket every copy of a value, which is exactly how you answer "how many times does this appear?" in one logarithmic sweep.
Implement two functions:
Reuse the lower_bound you wrote in the previous step.
def search(arr, target):
lo, hi = 0, len(arr) - 1
while lo <= hi:
mid = (lo + hi) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
lo = mid + 1
else:
hi = mid - 1
return -1
def lower_bound(arr, target):
lo, hi = 0, len(arr)
while lo < hi:
mid = (lo + hi) // 2
if arr[mid] < target:
lo = mid + 1
else:
hi = mid
return lo
def upper_bound(arr, target):
"""Return the index of the first element > target, or len(arr)."""
# TODO: like lower_bound but move lo past elements <= target.
pass
def count(arr, target):
"""Return how many times target occurs, via upper_bound - lower_bound."""
# TODO: return upper_bound(arr, target) - lower_bound(arr, target).
pass
The editor and the test runner need a wide screen. Open this page on a desktop browser and your progress will be waiting.
lower_bound found the first element that is at least target. upper_bound is its twin: it returns the index of the first element strictly greater than target. Together they bracket every copy of a value, which is exactly how you answer "how many times does this appear?" in one logarithmic sweep.
Implement two functions:
Reuse the lower_bound you wrote in the previous step.
Press Run Tests or ⌘↩ to check your solution.