Search in Rotated Sorted Array

LeetCode

LeetCode: https://leetcode.com/problems/search-in-rotated-sorted-array/

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