Recall valid inputs such as
[0 1 2 4 5 6 7]
[4 5 6 7 8 9 0 1 2]
- Loop invariant: closed searching interval [low, high] must include target if it exists.
- Input may be ascending or ascending-drop-ascending. For either case, if nums[mid] <= nums[-1] (last element), right half is ordered, else left half is ordered.
- Ordered half enables constant-time check for whether target is in the ordered half ("nums[low] <= target < nums[mid]" or "nums[mid] < target <= nums[high]") or the other unordered half. Hence binary search is possible.
- Search in Rotated Sorted Array II
What if duplicates are allowed?
My follow-up explanations:
class Solution(object): def search(self, nums, target): low = 0 high = len(nums) - 1 while low <= high: mid = (high - low) / 2 + low if nums[mid] == target: return mid else: # Right half is ascending. if nums[mid] <= nums[-1]: # Target is in right half. if nums[mid] < target <= nums[high]: low = mid + 1 # Target is in left half. else: high = mid - 1 # Left half is ascending. else: # Target is in left half. if nums[low] <= target < nums[mid]: high = mid - 1 # Target is in right half. else: low = mid + 1 return -1