grid47 Exploring patterns and algorithms
Oct 29, 2024
5 min read
Solution to LeetCode 81: Search in Rotated Sorted Array II Problem
You are given a sorted integer array nums that has been rotated at an unknown pivot index k. The array may contain duplicates. Your task is to determine whether a given target exists in the array, minimizing the number of operations as much as possible.
Problem
Approach
Steps
Complexity
Input: The input consists of a rotated sorted integer array `nums` and an integer target to search for in the array.
Example: nums = [4,5,6,6,7,0,1,2,4], target = 0
Constraints:
• 1 <= nums.length <= 5000
• -104 <= nums[i] <= 104
• -104 <= target <= 104
Output: Return `true` if the target exists in the array, otherwise return `false`.
Example: true
Constraints:
• The result should be true if the target exists in the array, and false if not.
Goal: To efficiently search for the target in the rotated sorted array, even when duplicates are present.
Steps:
• Use a modified binary search to handle both rotated arrays and duplicates.
• At each step, check if the middle element equals the target. If it does, return true.
• If the left, middle, and right elements are the same, increment `l` and decrement `r` to avoid duplicates.
• Use the standard binary search logic to narrow down the search range based on the sorted portion of the array.
Goal: The problem constraints guarantee that the array is rotated, but it may contain duplicates.
Steps:
• 1 <= nums.length <= 5000
• nums may contain duplicate values.
• The target is an integer in the range [-104, 104].
Assumptions:
• The array is guaranteed to be rotated, but duplicates may be present.
• Input: nums = [4,5,6,6,7,0,1,2,4], target = 0
• Explanation: The target `0` is found at index 5, so the output is `true`.
• Input: nums = [1,3,5,7,8,8,10], target = 4
• Explanation: The target `4` does not exist in the array, so the output is `false`.
Approach: We use a modified binary search approach that accounts for the rotation and potential duplicates in the array.
Observations:
• Binary search can be adapted to handle the rotated sorted array, but we need to handle duplicates carefully.
• When elements are equal at the left, middle, and right indices, we need to increment and decrement `l` and `r` respectively to avoid redundant checks.
Steps:
• Initialize left (`l`) to 0 and right (`r`) to `nums.size() - 1`.
• While `l` is less than or equal to `r`, calculate the middle index `mid`.
• If `nums[mid]` equals the target, return `true`.
• If `nums[l] == nums[mid] == nums[r]`, increment `l` and decrement `r` to handle duplicates.
• If the left half is sorted, check if the target lies within this range. If so, update `r`. Otherwise, update `l`.
• If the right half is sorted, check if the target lies within this range. If so, update `l`. Otherwise, update `r`.
Empty Inputs:
• If the array is empty, the result should be false.
Large Inputs:
• Ensure that the solution handles the largest possible input size efficiently.
Special Values:
• Handle cases where all elements are the same and the target is present or absent.
Constraints:
• Ensure that the solution works within the time and space limits for large arrays.
boolsearch(vector<int>& nums, int target) {
int left =0, right = nums.size() -1;
while (left <= right) {
int mid = left + (right - left) /2;
if (nums[mid] == target) {
returntrue;
}
// If left half is sorted
if (nums[left] <= nums[mid]) {
if (target >= nums[left] && target < nums[mid]) {
right = mid -1;
} else {
left = mid +1;
}
} else {
// Right half is sorted
if (target > nums[mid] && target <= nums[right]) {
left = mid +1;
} else {
right = mid -1;
}
}
}
returnfalse;
}
1 : Function Declaration
boolsearch(vector<int>& nums, int target) {
Declares a function `search` that takes a sorted rotated array `nums` and a target value `target` as input and returns a boolean indicating whether the target is found.
2 : Variable Initialization
int left =0, right = nums.size() -1;
Initializes two pointers, `left` and `right`, to the beginning and end of the array, respectively.
3 : Loop Iteration
while (left <= right) {
Starts a `while` loop that continues as long as `left` is less than or equal to `right`.
4 : Calculation
int mid = left + (right - left) /2;
Calculates the middle index `mid` using a formula that avoids potential integer overflow.
5 : Conditional
if (nums[mid] == target) {
returntrue;
}
Checks if the element at the middle index is the target. If so, returns `true`.
6 : Conditional
if (nums[left] <= nums[mid]) {
Checks if the left half of the array is sorted.
7 : Conditional
if (target >= nums[left] && target < nums[mid]) {
right = mid -1;
} else {
left = mid +1;
}
If the left half is sorted and the target is within its range, adjusts the `right` pointer. Otherwise, adjusts the `left` pointer.
8 : Conditional
} else {
If the left half is not sorted, the right half must be sorted.
9 : Conditional
if (target > nums[mid] && target <= nums[right]) {
left = mid +1;
} else {
right = mid -1;
}
If the right half is sorted and the target is within its range, adjusts the `left` pointer. Otherwise, adjusts the `right` pointer.
10 : Return
returnfalse;
If the target is not found after the loop, returns `false`.
Best Case: O(log n)
Average Case: O(log n)
Worst Case: O(n)
Description: In the worst case, we may need to check every element due to duplicates, leading to linear time complexity.
Best Case: O(1)
Worst Case: O(1)
Description: The solution uses constant space, as we are modifying the search range in-place.
