18. Search in Rotated Sorted Array

#leetcode/33

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.

Example:

Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4

Solution

Solution in C++ using recursion

The idea is similar to 17. Find Minimum in Rotated Sorted Array, with some changes. There are several cases to consider:

1. If i > j, it means the search range is empty, and the target element is not found in the array. In this case, -1 is returned to indicate that the target is not present.
2. If the target element is equal to nums[m], it means the target is found at index m, and m is returned as the result.
3. If nums[m] > nums[j], it suggests that the pivot point (where the array was rotated) is somewhere to the right of m. In this case, two conditions are checked:
   • If target >= nums[m] or target <= nums[j], it means that the target lies in the right subarray. The search is continued in the right subarray by calling searchRec recursively with the range from m + 1 to j.
     You can see this with nums = [1,2,3,4,0], target = 3 and with nums = [2,3,4,0,1], target = 0.
4. If nums[m] < nums[j], it suggests that the pivot point is somewhere to the left of m. In this case, two conditions are checked:
   • If target >= nums[m] and target <= nums[j], it means that the target lies in the right subarray. The search is continued in the right subarray by calling searchRec recursively with the range from m + 1 to j.
     You can see this with nums = [0,1,2,3,4], target = 3.
5. If none of the above conditions are met, it means that the target is in the left subarray. The search is continued in the left subarray by calling searchRec recursively with the range from i to m - 1.

Here's the implementation.

int search(vector<int>& nums, int target) {
	return searchRec(nums, 0, nums.size() - 1, target);
}
int searchRec(vector<int>& nums, int i, int j, int target) {
	int m = (i + j) / 2;
	if(i > j)
		return -1;
	else if(target == nums[m])
	   return m;
	else if(nums[m] > nums[j] &&
			(target >= nums[m] ||
			target <= nums[j])
			)
		return searchRec(nums, m + 1, j, target);
	else if(nums[m] < nums[j] &&
		(target >= nums[m] &&
		target <= nums[j])
		)
	return searchRec(nums, m + 1, j, target);
	else    
		return searchRec(nums, i, m - 1, target);
}

• Time complexity: $O(log(n))$ (where n is the size of the vector)
• Space complexity: $O(log(n))$ (we are using recursion)

Solution in C++ without recursion

For the sake of completeness, here's the iterative implementation.

int findMin(vector<int>& nums) {
	int i = 0, j = nums.size() - 1;

	while(i <= j) {
		int m = (i + j) / 2;
		if(nums[m] == target)
			return m;
		else if(nums[m] > nums[j] && (target >= nums[m] || target <= nums[j]))
			i = m + 1;
		else if(nums[m] < nums[j] && target >= nums[m] && target <= nums[j])
			i = m + 1;
		else
			j = m - 1;
	}
	return -1;
}

• Time complexity: $O(log(n))$ (where n is the size of the vector)
• Space complexity: $O(1)$