A sorted array of distinct integers was rotated at some unknown pivot, so [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]. Given the rotated array nums and a value target, return its index or -1 if it is absent. You must do it in O(log n).
- 1 <= nums.length <= 5000
- -10^4 <= nums[i], target <= 10^4
- All values are distinct
- `nums` is a possibly rotated sorted array
Give it a real try first. Even 15 minutes of struggle makes the solution stick far better.
Intuition
A linear scan is O(n). The array is no longer sorted overall, but cutting it at any mid gives two halves where at least one is sorted (the rotation point can only be in one of them). For the sorted half we can check in O(1) whether target falls inside its range. If it does, search that half; if not, the target can only be in the other half. Each step still discards half the array, so the search stays O(log n).
Algorithm
- Set
lo = 0,hi = n - 1. Whilelo <= hi, computemid. - If
nums[mid] == target, returnmid. - If
nums[lo] <= nums[mid](left half sorted): ifnums[lo] <= target < nums[mid], sethi = mid - 1, elselo = mid + 1. - Otherwise the right half is sorted: if
nums[mid] < target <= nums[hi], setlo = mid + 1, elsehi = mid - 1. - Return
-1if the loop ends.
O(log n)Space: O(1)<= in nums[lo] <= nums[mid]. When lo == mid (two elements left), the left "half" is a single element and counts as sorted; using < sends you the wrong way. A common follow-up is the version with duplicates (Search in Rotated Sorted Array II).class Solution: def search(self, nums: List[int], target: int) -> int: lo, hi = 0, len(nums) - 1 while lo <= hi: mid = (lo + hi) // 2 if nums[mid] == target: return mid if nums[lo] <= nums[mid]: # left half [lo..mid] is sorted if nums[lo] <= target < nums[mid]: hi = mid - 1 else: lo = mid + 1 else: # right half [mid..hi] is sorted if nums[mid] < target <= nums[hi]: lo = mid + 1 else: hi = mid - 1 return -1