grid47 Exploring patterns and algorithms
Nov 3, 2024
7 min read
Solution to LeetCode 33: Search in Rotated Sorted Array Problem
You are given a sorted array ’nums’ which may have been rotated at an unknown pivot. Your task is to search for a target value in this rotated array. Return the index of the target if found, or -1 if not found. The solution must have a runtime complexity of O(log n).
Problem
Approach
Steps
Complexity
Input: The input is a rotated sorted array 'nums' of distinct integers, followed by the target value to search for.
Example: nums = [4, 5, 6, 7, 0, 1, 2], target = 0
Constraints:
• 1 <= nums.length <= 5000
• -104 <= nums[i] <= 104
• All values of nums are unique.
• nums is a rotated sorted array.
• -104 <= target <= 104
Output: The output is the index of the target in the rotated array if it exists, otherwise return -1.
Example: For nums = [4, 5, 6, 7, 0, 1, 2], target = 0, the output is 4.
Constraints:
Goal: The goal is to search for the target value in the rotated array efficiently using binary search.
Steps:
• Use binary search to find the pivot where the rotation occurs.
• Determine which half of the array is sorted, and narrow down the search to that half.
• Adjust the search range depending on whether the target is within the sorted half.
Goal: The array is rotated at some unknown index, and the array contains distinct elements. We need to ensure that the solution operates in O(log n) time.
Steps:
• The array contains at least one element.
• The array length is between 1 and 5000.
• Each element is distinct.
Assumptions:
• The array has been rotated, and the array is sorted in ascending order before the rotation.
• Input: nums = [4, 5, 6, 7, 0, 1, 2], target = 0
• Explanation: The array is rotated at index 3, so the target value 0 is found at index 4 in the rotated array.
• Input: nums = [4, 5, 6, 7, 0, 1, 2], target = 3
• Explanation: The target value 3 does not exist in the array, so the output is -1.
Approach: We will use a modified binary search to efficiently find the target in the rotated array.
Observations:
• The array is rotated, so we cannot perform a standard binary search directly.
• We need to identify which half of the array is sorted and determine if the target is within that range.
• The key observation is that the array is always divided into two subarrays, one of which is sorted.
Steps:
• Start with the entire array and calculate the midpoint.
• Check if the left side is sorted by comparing the first element with the midpoint.
• If the target is within the sorted half, adjust the search range accordingly.
• Otherwise, search in the unsorted half and continue narrowing down the search space.
Empty Inputs:
• The array is guaranteed to have at least one element, so no need to handle empty arrays.
Large Inputs:
• The solution should handle arrays with up to 5000 elements efficiently within O(log n) time.
Special Values:
• If the target is not present in the array, return -1.
Constraints:
• All elements are distinct, so we do not need to worry about duplicate values.
intsearch(vector<int>& nums, int target) {
int n = nums.size();
int s =0, e = n -1;
while(s <= e) {
int mid = s + (e - s +1) /2;
if(nums[mid] == target) return mid;
if(nums[s] <= nums[mid]) {// window contain jerk
if(nums[s] <= target && target < nums[mid])
e = mid -1;
else s = mid +1;
} else {// window is linear
if(nums[mid] < target && target <= nums[e])
s = mid +1;
else e = mid -1;
}
}
return-1;
}
1 : Function Declaration
intsearch(vector<int>& nums, int target) {
This line declares a function named 'search' that takes a vector of integers 'nums' and a target integer 'target' as input and returns the index of the target element if found, otherwise -1.
2 : Variable Initialization
int n = nums.size();
This line stores the size of the input array 'nums' in the variable 'n'.
3 : Variable Initialization
int s =0, e = n -1;
This line initializes two pointers 's' and 'e' to represent the start and end indices of the search range, respectively.
4 : Loop Iteration
while(s <= e) {
This line starts a `while` loop that continues as long as the start index 's' is less than or equal to the end index 'e'.
5 : Calculation
int mid = s + (e - s +1) /2;
This line calculates the middle index 'mid' using a formula that avoids integer overflow for large values of 's' and 'e'.
6 : Conditional Check
if(nums[mid] == target) return mid;
This line checks if the element at the middle index 'mid' is equal to the target. If so, the function returns the index 'mid'.
7 : Conditional Check
if(nums[s] <= nums[mid]) {// window contain jerk
This line checks if the first half of the array is sorted. If it is, the window contains a 'jerk' (a point where the array is not sorted).
8 : Conditional Check
if(nums[s] <= target && target < nums[mid])
This line checks if the target lies within the sorted first half of the array.
9 : Index Update
e = mid -1;
If the target lies within the sorted first half, the search space is narrowed by updating the end index 'e' to 'mid - 1'.
10 : Index Update
else s = mid +1;
If the target doesn't lie within the sorted first half, the search space is narrowed by updating the start index 's' to 'mid + 1'.
11 : Conditional Check
} else {// window is linear
This line checks if the second half of the array is sorted. If it is, the window is linear.
12 : Conditional Check
if(nums[mid] < target && target <= nums[e])
This line checks if the target lies within the sorted second half of the array.
13 : Index Update
s = mid +1;
If the target lies within the sorted second half, the search space is narrowed by updating the start index 's' to 'mid + 1'.
14 : Index Update
else e = mid -1;
If the target doesn't lie within the sorted second half, the search space is narrowed by updating the end index 'e' to 'mid - 1'.
15 : Return
return-1;
If the target is not found after the loop, the function returns -1 to indicate that the target is not present in the array.
Best Case: O(log n)
Average Case: O(log n)
Worst Case: O(log n)
Description: The time complexity is O(log n) because we are using a modified binary search that halves the search space at each step.
Best Case: O(1)
Worst Case: O(1)
Description: The space complexity is O(1) because the algorithm only uses a constant amount of extra space.
