Search in Rotated Sorted Array
Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand. (i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]). You are given an array of integers nums and an integer target. If the target is found in the array, return its index, otherwise, return -1.
Constraints:
- 1 <= nums.length <= 5000
- -10^4 <= nums[i] <= 10^4
- nums is guaranteed to be rotated at some pivot.
- -10^4 <= target <= 10^4
Examples:
Input: [4,5,6,7,0,1,2], 0
Output: 4
Explanation: The target 0 is found at index 4 in the rotated array.
Solutions
Modified Binary Search
The solution uses a modified binary search algorithm to find the target in the rotated 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 it is, it updates the right pointer. If not, it updates the left pointer. If the left half is not sorted, it checks if the target is in the right half and updates the pointers accordingly.
class Solution {
public:
int search(vector<int>& nums, int target) {
int left = 0;
int right = nums.size() - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) return mid;
if (nums[left] <= nums[mid]) {
if (nums[left] <= target && target < nums[mid]) {
right = mid - 1;
}
else {
left = mid + 1;
}
}
else {
if (nums[mid] < target && target <= nums[right]) {
left = mid + 1;
}
else {
right = mid - 1;
}
}
}
return -1;
}
}
;Follow-up:
What if the array is not rotated, how would you solve it?
