A sorted array that has been rotated, such as [4, 5, 6, 7, 0, 1, 2], is not sorted any more, yet binary search still works with a twist: whichever half you split it into, at least one half is properly sorted, and you can check whether the target lies inside that sorted half.
Given a list nums of distinct integers that was sorted ascending and then rotated at some unknown pivot, and an integer target, return the index of target, or -1 if it is not present.
Examples
Input: nums = [4, 5, 6, 7, 0, 1, 2], target = 0
Output: 4
Input: nums = [4, 5, 6, 7, 0, 1, 2], target = 3
Output: -1
Input: nums = [1], target = 0
Output: -1
Constraints
1 <= len(nums) <= 5000- All values are distinct. The rotation may be by zero positions (already sorted).
- Aim for O(log n) time.
Goals
- Recognise that at least one half of a rotated sorted array is still sorted
- Decide which half is sorted by comparing nums[lo] with nums[mid]
- Use a range check on the sorted half to decide where to continue searching