The most powerful use of binary search is not searching a list at all. When a yes/no test is monotonic, meaning it is False for small values and then flips to True and stays True, you can binary search the numeric answer itself. This is how you solve problems like "the minimum speed that finishes the work in time."
Implement first_true(lo, hi, predicate):
The tests use this to find a minimum eating speed: the smallest speed s such that the total hours needed to finish the piles fits within the time limit.
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):
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 count(arr, target):
return upper_bound(arr, target) - lower_bound(arr, target)
def search_rotated(arr, target):
lo, hi = 0, len(arr) - 1
while lo <= hi:
mid = (lo + hi) // 2
if arr[mid] == target:
return mid
if arr[lo] <= arr[mid]:
if arr[lo] <= target < arr[mid]:
hi = mid - 1
else:
lo = mid + 1
else:
if arr[mid] < target <= arr[hi]:
lo = mid + 1
else:
hi = mid - 1
return -1
def first_true(lo, hi, predicate):
"""Return the smallest x in [lo, hi] with predicate(x) True, or hi + 1 if none.
Assumes predicate is monotonic: once True it stays True as x grows.
"""
# TODO: binary search the boundary. When predicate(mid) is True, keep mid as a
# candidate (hi = mid); otherwise search higher (lo = mid + 1).
pass
The editor and the test runner need a wide screen. Open this page on a desktop browser and your progress will be waiting.
The most powerful use of binary search is not searching a list at all. When a yes/no test is monotonic, meaning it is False for small values and then flips to True and stays True, you can binary search the numeric answer itself. This is how you solve problems like "the minimum speed that finishes the work in time."
Implement first_true(lo, hi, predicate):
The tests use this to find a minimum eating speed: the smallest speed s such that the total hours needed to finish the piles fits within the time limit.
Press Run Tests or ⌘↩ to check your solution.