The problem
A sorted array of distinct integers has been rotated at an unknown point (see the previous problem). Given a target, return its index, or −1 if it is absent, in O(log n) time.
Examples
01
- Input
nums = [4, 5, 6, 7, 0, 1, 2], target = 0
- Output
4
02
- Input
nums = [4, 5, 6, 7, 0, 1, 2], target = 3
- Output
-1
03
- Input
nums = [1], target = 0
- Output
-1
Constraints
- 1 ≤ nums.length ≤ 5000
- −10⁴ ≤ nums[i], target ≤ 10⁴
- All values are distinct.
The idea
Split the range at mid. However the array was rotated, at least one of the two halves is sorted — the one not containing the drop. A sorted half is easy to test: the target is in it exactly when it lies between the half’s end values.
So find the sorted half (nums[lo] ≤ nums[mid] means the left one), check whether the target falls inside it, and keep that half or the other. Each step still halves the range.
- Time
- O(log n)
- Space
- O(1)
Solution
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]: # the left half lo..mid is sorted if nums[lo] <= target < nums[mid]: hi = mid - 1 else: lo = mid + 1 else: # the right half mid..hi is sorted if nums[mid] < target <= nums[hi]: lo = mid + 1 else: hi = mid - 1 return -1