Search in Rotated Sorted Array II
Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand. (i.e., [0,0,1,2,2,5,6] might become [2,5,6,0,0,1,2]). You are given a target value to search. If found in the array return true, otherwise return false.
Constraints:
- 1 <= nums.length <= 5000
- -10^4 <= nums[i] <= 10^4
- nums is sorted in non-decreasing order before any rotation
- 1 <= target <= 10^4
Examples:
Input: nums = [2,5,6,0,0,1,2], target = 0
Output: true
Explanation: The target 0 is present in the array.
Input: nums = [2,5,6,0,0,1,2], target = 3
Output: false
Explanation: The target 3 is not present in the array.
Solutions
Modified Binary Search
The solution uses a modified binary search approach to find the target in the rotated sorted array. It first checks if the middle element is the target. If not, it checks if the left half is sorted. If it is, it checks if the target is in the left half. If not, it checks the right half. If the left half is not sorted, it checks the right half. The process continues until the target is found or the search space is exhausted.
def search(nums, target):
left, right = 0, len(nums) - 1
while left <= right:
mid = (left + right) // 2
if nums[mid] == target:
return True
if nums[left] == nums[mid] == nums[right]:
left += 1
right -= 1
elif nums[left] <= nums[mid]:
if nums[left] <= target < nums[mid]:
right = mid - 1
else:
left = mid + 1
else:
if nums[mid] < target <= nums[right]:
left = mid + 1
else:
right = mid - 1
return FalseFollow-up:
Search in Rotated Sorted Array III: What if the array is rotated multiple times?
