Sometimes a sorted array has been rotated around an unknown pivot, for example [4, 5, 6, 7, 0, 1, 2]. It is no longer globally sorted, so plain search breaks. The key insight: at any midpoint, at least one of the two halves is still sorted, and you can test in O(1) whether the target lies inside that sorted half.
Implement search_rotated(arr, target) for an array of distinct values:
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):
"""Return the index of target in a rotated sorted array (distinct values), or -1."""
# TODO: at each mid, one half is sorted. Decide which half holds 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.
Sometimes a sorted array has been rotated around an unknown pivot, for example [4, 5, 6, 7, 0, 1, 2]. It is no longer globally sorted, so plain search breaks. The key insight: at any midpoint, at least one of the two halves is still sorted, and you can test in O(1) whether the target lies inside that sorted half.
Implement search_rotated(arr, target) for an array of distinct values:
Press Run Tests or ⌘↩ to check your solution.