Search in Rotated Sorted Array

01 · Question

There is an integer array nums sorted in ascending order (with distinct values), and rotated. Given the array and an integer target, return the index of target or -1 if it is not found.

Example:

Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4

02 · Solution

Reference solution

1def search(nums: List[int], target: int) -> int:
2    l, r = 0, len(nums) - 1
3    
4    while l <= r:
5        mid = (l + r) // 2
6        
7        if nums[mid] == target:
8            return mid
9        
10        if nums[l] <= nums[mid]:
11            if nums[l] <= target < nums[mid]:
12                r = mid - 1
13            else:
14                l = mid + 1
15        else:
16            if nums[mid] < target <= nums[r]:
17                l = mid + 1
18            else:
19                r = mid - 1
20                
21    return -1

Find Minimum in Rotated Sorted Array

Valley Bottom