33. Search in Rotated Sorted Array — LeetCode(Python)
I got you!
Problem:
There is an integer array nums
sorted in ascending order (with distinct values).
Prior to being passed to your function, nums
is possibly rotated at an unknown pivot index k
(1 <= k < nums.length
) such that the resulting array is [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]
(0-indexed). For example, [0,1,2,4,5,6,7]
might be rotated at pivot index 3
and become [4,5,6,7,0,1,2]
.
Given the array nums
after the possible rotation and an integer target
, return the index of target
if it is in nums
, or -1
if it is not in nums
.
You must write an algorithm with O(log n)
runtime complexity.
Example 1:
Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4
Example 2:
Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1
Example 3:
Input: nums = [1], target = 0
Output: -1
Constraints:
1 <= nums.length <= 5000
-104 <= nums[i] <= 104
- All values of
nums
are unique. nums
is an ascending array that is possibly rotated.-104 <= target <= 104
Solution:
l, r = 0, len(nums) - 1
while l <= r:
mid = (l + r) // 2
if nums[mid] == target:
return mid
if nums[mid] >= nums[l]: #we are in the left sorted portion
if target > nums[mid] or target < nums[l]: #target is not in left subarray
l = mid + 1 #so go to right subarray
else:
r = mid - 1
elif nums[mid] <= nums[r]: #right sorted portion
if target < nums[mid] or target > nums[r]: #target is not in right subarray
r = mid - 1 #so check in left
else:
l = mid + 1
return -1
Explanation —
We use binary search here. We are given a sorted array that has been rotated a given number of times.
We perform a basic binary search on the array.
Consider the following array for better understanding while going through the points below:
[4,5,6,7,0,1,2]
- First, we come to the mid element of the array nums. We return mid if nums[mid] == target.
- If this element is greater than the number at the left pointer, we are in the left sorted array.
- If the target value is not in this left subarray, we check the right subarray by shifting our left pointer.
- If the target value is in this subarray, we shift our right pointer to the end of this subarray.
- Else if this element is smaller than the number at the right pointer, we are in the right sorted array.
- In this case, if the target value is not in the right sorted array, we shift our right pointer to only check the left portion of the array.
- If, however, the target value is in this subarray, we shift our left pointer to the beginning of this subarray.
Finally, we return -1 if we terminate the while loop.
Time and Space Complexity —
Since, this is a binary search procedure, our time and space complexities are the same.
Thus, if n is the length of the array nums,
Time Complexity: O(log(n))
Space Complexity: O(1)