Search In Rotated Sorted Array - Leetcode Solution

The "Search in Rotated Sorted Array" problem on LeetCode is a problem where the task is to search for a target value in a sorted array that has been rotated at some unknown pivot point.

Here is the detailed solution for the problem:

Approach:

The problem specifies that the input array is sorted, but it has been rotated at some unknown pivot point. So, the first thing we need to do is find the pivot point - the index at which the array was rotated. We can then divide the input array into two sub-arrays at this point and search for the target value in one of the sub-arrays, depending on which sub-array the target value is expected to be in.

We can find the pivot point using a slightly modified binary search algorithm. We start by checking the middle element of the input array. If this element is greater than the last element of the array, we know that the pivot point must be somewhere to the right of this element. Otherwise, we know that the pivot point must be somewhere to the left of this element. We keep dividing the input array in half until we find the pivot point.

Once we have found the pivot point, we can search for the target value using another binary search algorithm. We again start by checking the middle element of the relevant sub-array and divide the array in half until we find the target value, or we determine that the target value is not in the sub-array.

Algorithm:

1. Initialize the left and right indices to the first and last elements of the input array, respectively.
2. While the left index is less than or equal to the right index, do the following: a. Calculate the middle index of the input array. b. If the middle element is equal to the target value, return the middle index. c. If the middle element is greater than the last element of the array, update the left index to the middle index + 1. Otherwise, update the right index to the middle index - 1.
3. If we have not found the pivot point by the end of the loop, the input array must be sorted in ascending order. Return 0 as the pivot index.
4. Set the pivot index to the last value of the left index before the loop ended.
5. If the target value is greater than or equal to the first element of the input array and less than or equal to the last element of the left sub-array, perform binary search on the left sub-array. Otherwise, perform binary search on the right sub-array.
6. For binary search, initialize the left and right indices to the first and last elements of the relevant sub-array, respectively.
7. While the left index is less than or equal to the right index, do the following: a. Calculate the middle index of the sub-array. b. If the middle element is equal to the target value, return the middle index. c. If the middle element is less than the target value, update the left index to the middle index + 1. Otherwise, update the right index to the middle index - 1.
8. If we have not found the target value by the end of the loop, return -1.

Code Implementation:

class Solution { public: int search(vector<int>& nums, int target) { int n = nums.size(); int left = 0, right = n - 1; int pivot = -1; while (left <= right) { int mid = (left + right) / 2; if (nums[mid] == target) { return mid; } if (nums[mid] > nums[n - 1]) { left = mid + 1; } else { right = mid - 1; } } pivot = left - 1; left = 0, right = pivot; while (left <= right) { int mid = (left + right) / 2; if (nums[mid] == target) { return mid; } if (nums[mid] < target) { left = mid + 1; } else { right = mid - 1; } } left = pivot + 1, right = n - 1; while (left <= right) { int mid = (left + right) / 2; if (nums[mid] == target) { return mid; } if (nums[mid] < target) { left = mid + 1; } else { right = mid - 1; } } return -1; } };

Time Complexity:

The worst-case time complexity of this algorithm is O(log n), as we are performing binary search twice - once to find the pivot point, and once to search for the target value.

Space Complexity:

The space complexity of this algorithm is O(1), as we are not using any extra data structures to perform the search.

1