Search in Rotated Sorted Array

Write `search_rotated(nums, target)` returning the index of the target in a rotated ascending array of distinct values, or `-1`. search_rotated([4, 5, 6, 7, 0, 1, 2], 0) -> 4 search_rotated([4, 5, 6, 7, 0, 1, 2], 3) -> -1 At any midpoint, at least one half is properly sorted. Work out which, then ask whether the target falls inside that half's range: if it does, search there, otherwise search the other one. Use inclusive comparisons on the sorted half's endpoints or you will lose the target when it sits exactly on a boundary.