Leetcode 33 - Search in Rotated Sorted Array
| Array | Binary Search |
Leetcode Link for Search in Rotated Sorted Array
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.
You must write an algorithm with O(log n) runtime complexity.
Example 1:
Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4
Example 2:
Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1
Example 3:
Input: nums = [1], target = 0
Output: -1
Constraints:
-
1 <= nums.length <= 5000
-
-104 <= nums[i] <= 104
-
All values of nums are unique.
-
nums is an ascending array that is possibly rotated.
-
-104 <= target <= 104
Solution:
Iterative Approach:
public int search(int[] nums, int target) {
int left = 0;
int right = nums.length -1;
while(left <= right){
int mid = left + (right - left)/2;
if(target == nums[mid])
return mid;
if(nums[left] <= nums[mid] )
{
if(target >= nums[left] && target < nums[mid]){
right = mid -1;
}
else
{
left = mid +1;
}
} //right is sorted
else{
if(target > nums[mid] && target <= nums[right]){
left = mid+1;
}
else{
right = mid -1;
}
}
}
return -1;
}
Methodology:
Initialization: It starts by initializing two pointers, left and right, which represent the bounds of the search space.
Binary Search: Using a binary search approach, the function calculates the midpoint (mid) between left and right.
Comparison:
If the target is equal to nums[mid], the function returns the index mid.
If the left subarray (nums[left] to nums[mid]) is sorted:
It checks if the target lies within this sorted subarray and adjusts the right pointer accordingly.
Otherwise, it moves the left pointer.
If the right subarray (nums[mid] to nums[right]) is sorted:
It checks if the target lies within this sorted subarray and adjusts the left pointer accordingly.
Otherwise, it moves the right pointer.
Termination: If the target is not found, the function returns -1.
Efficiency: The algorithm efficiently narrows down the search space in logarithmic time, making it suitable for large arrays.
Time Complexity:
The time complexity for the iterative approach is 𝑂(log𝑛), where 𝑛is the number of elements in the array.
This is because the algorithm repeatedly divides the search space in half until it finds the target element or determines that the target is not in the array.
Space Complexity:
The space complexity for the iterative approach is 𝑂(1).
This is because it uses a constant amount of additional space for variables like left, right, and mid, regardless of the size of the input array.
Recursive Approach:
public int search(int[] nums, int target) {
return searchHelper(nums, target, 0, nums.length - 1);
}
private int searchHelper(int[] nums, int target, int left, int right) {
if (left > right) {
return -1;
}
int mid = left + (right - left) / 2;
if (target == nums[mid]) {
return mid;
}
// If the left half is sorted
if (nums[left] <= nums[mid]) {
if (target >= nums[left] && target < nums[mid]) {
return searchHelper(nums, target, left, mid - 1);
} else {
return searchHelper(nums, target, mid + 1, right);
}
} else { // If the right half is sorted
if (target > nums[mid] && target <= nums[right]) {
return searchHelper(nums, target, mid + 1, right);
} else {
return searchHelper(nums, target, left, mid - 1);
}
}
}
Methodology:
In this version, the search function simply calls a helper function searchHelper with the initial left and right bounds of the array. The searchHelper function then performs the binary search recursively, following the same logic as your iterative version. If the target element is found, it returns the index; otherwise, it returns -1.
Time Complexity:
The time complexity for the recursive approach is also 𝑂(log𝑛)
for the same reason as the iterative approach—it reduces the search space by half with each recursive call.
Space Complexity:
The space complexity for the recursive approach is 𝑂(log𝑛)
due to the call stack. In the worst case, the depth of the recursive call stack will be proportional to the logarithm of the number of elements in the array.
Comparison:
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Iterative | O(logn) | O(1) |
| Recursive | O(logn) | O(logn) |
Both approaches have the same time complexity, but the iterative approach has an advantage in space complexity since it doesn’t use additional stack space for recursion.
Author: Mohammad J Iqbal
