Table of Contents
Problem Description:
Suppose you have a sorted array of distinct integers that has been rotated at some unknown pivot index. You need to find the index of the target element target in the rotated sorted array. If the target element is not present in the array, return -1.
You can assume that the array does not contain duplicates, and the elements are in ascending order.
Sample Input and Expected Output:
Input:
rotatedArray = [4, 5, 6, 7, 0, 1, 2]
target = 0
Output:
Index of target element 0: 4
Input:
rotatedArray = [4, 5, 6, 7, 0, 1, 2]
target = 3
Output:
Target element 3 not found in the rotated sorted array.
Solution in C++:
We can solve this problem using a modified binary search algorithm. We can identify whether the target element lies in the left or right half of the rotated array based on a comparison with the first element. Then, we can perform a regular binary search in the corresponding half to find the target element.
#include <iostream>
#include <vector>
int searchInRotatedSortedArray(std::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;
}
// Check if the left half is sorted
if (nums[left] <= nums[mid]) {
if (target >= nums[left] && target < nums[mid]) {
right = mid - 1;
} else {
left = mid + 1;
}
}
// Check if the right half is sorted
else {
if (target > nums[mid] && target <= nums[right]) {
left = mid + 1;
} else {
right = mid - 1;
}
}
}
return -1;
}
int main() {
std::vector<int> rotatedArray = {4, 5, 6, 7, 0, 1, 2};
int target1 = 0;
int target2 = 3;
int index1 = searchInRotatedSortedArray(rotatedArray, target1);
int index2 = searchInRotatedSortedArray(rotatedArray, target2);
if (index1 != -1) {
std::cout << "Index of target element " << target1 << ": " << index1 << std::endl;
} else {
std::cout << "Target element " << target1 << " not found in the rotated sorted array." << std::endl;
}
if (index2 != -1) {
std::cout << "Index of target element " << target2 << ": " << index2 << std::endl;
} else {
std::cout << "Target element " << target2 << " not found in the rotated sorted array." << std::endl;
}
return 0;
}
Time Complexity and Space Complexity:
The time complexity of the solution is O(log n), where n is the size of the rotatedArray. This is because we are performing a binary search, and at each step, we reduce the search space by half.
The space complexity is O(1) as we are using a constant amount of additional space for variables in the solution, regardless of the size of the input array.