Search in Rotated Sorted Array

LeetCode

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
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
Previous
Find Minimum in Rotated Sorted Array
Next
Valley Bottom
l
4
0
5
1
6
2
mid
7
3
0
4
1
5
r
2
6
target=0
Step 1 / 5
Step 1:
Initialize l=0, r=6. Compute mid=3.
Pointers: l=0, mid=3, r=6
Focus: select @ [0, 3, 6]
target=0