Search in Rotated Sorted Array II
MedPrompt
There is an integer array nums sorted in non-decreasing order (not necessarily with distinct values).
Before being passed to your function, nums is rotated at an unknown pivot index k (0 <= 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,4,4,5,6,6,7] might be rotated at pivot index 5 and become [4,5,6,6,7,0,1,2,4,4].
Given the array nums after the rotation and an integer target, return true if target is in nums, or false if it is not in nums.
You must decrease the overall operation steps as much as possible.
Example 1:
Input: nums = [2,5,6,0,0,1,2], target = 0
Output: trueExample 2:
Input: nums = [2,5,6,0,0,1,2], target = 3
Output: false
Constraints:
1 <= nums.length <= 5000-104 <= nums[i] <= 104numsis guaranteed to be rotated at some pivot.-104 <= target <= 104
Follow up: This problem is similar to Search in Rotated Sorted Array, but nums may contain duplicates. Would this affect the runtime complexity? How and why?
Approaches
2 approaches with complexity analysis and trade-offs.
The most straightforward approach is to iterate through each element of the array and check if it matches the target value. This method does not leverage the partially sorted nature of the array.
Algorithm
-
- Start a loop that iterates from the first element (
index = 0) to the last element (index = nums.length - 1).
- Start a loop that iterates from the first element (
-
- In each iteration, get the current element
nums[i].
- In each iteration, get the current element
-
- Compare the current element with the
target.
- Compare the current element with the
-
- If
nums[i] == target, the target is found. Returntrue.
- If
-
- If the loop finishes without finding any match, return
false.
- If the loop finishes without finding any match, return
Walkthrough
This brute-force method involves a simple loop that traverses the array from the first element to the last. In each iteration, it compares the current element with the target. If a match is found, the function immediately returns true. If the loop completes without finding the target, it means the target is not in the array, and the function returns false.
class Solution { public boolean search(int[] nums, int target) { for (int num : nums) { if (num == target) { return true; } } return false; }}Complexity
Time
O(N)
Space
O(1)
Trade-offs
Pros
Very simple to understand and implement.
Guaranteed to work correctly for any input array, regardless of its properties.
Cons
Highly inefficient, with a time complexity linear to the size of the array.
Fails to utilize the special property of the array (rotated sorted), missing an opportunity for optimization.
A more optimized approach uses a modified binary search algorithm. The standard binary search is adapted to handle the rotation and the presence of duplicates. The core idea is to identify a sorted subarray in each step and decide whether to search in that half or the other.
Algorithm
-
- Initialize pointers
left = 0andright = nums.length - 1.
- Initialize pointers
-
- Loop as long as
left <= right.
- Loop as long as
-
- Calculate
mid = left + (right - left) / 2.
- Calculate
-
- If
nums[mid] == target, returntrue.
- If
-
- If
nums[left] == nums[mid] && nums[mid] == nums[right], we cannot determine the sorted half. Shrink the search space by doingleft++andright--and continue to the next iteration.
- If
-
- Check if the left part (
nums[left]tonums[mid]) is sorted (nums[left] <= nums[mid]).
- Check if the left part (
-
- If it is, check if
targetis in the range[nums[left], nums[mid]).
- If it is, check if
-
- If yes, search in the left half:
right = mid - 1.
- If yes, search in the left half:
-
- If no, search in the right half:
left = mid + 1.
- If no, search in the right half:
-
- If the left part is not sorted, the right part (
nums[mid]tonums[right]) must be.
- If the left part is not sorted, the right part (
-
- Check if
targetis in the range(nums[mid], nums[right]].
- Check if
-
- If yes, search in the right half:
left = mid + 1.
- If yes, search in the right half:
-
- If no, search in the left half:
right = mid - 1.
- If no, search in the left half:
-
- If the loop terminates, the target was not found. Return
false.
- If the loop terminates, the target was not found. Return
Walkthrough
This approach uses two pointers, left and right, to define the current search space. In each step, we calculate the middle element mid. The main challenge introduced by duplicates is the case where nums[left] == nums[mid] == nums[right]. In this scenario, we cannot determine which half is sorted. For example, in [1, 0, 1, 1, 1] and [1, 1, 1, 0, 1], nums[left], nums[mid], and nums[right] are all 1. In the first case, the pivot is on the right; in the second, it's on the left. Since we can't make an informed decision, we shrink the search space by incrementing left and decrementing right. This handles the ambiguity at the cost of a potential O(N) worst-case runtime.
In other cases, at least one half of the array (from left to mid or mid to right) must be sorted. We check if nums[left] <= nums[mid]. If true, the left half is sorted. We then check if the target lies within this sorted range. If it does, we search in the left half (right = mid - 1); otherwise, we search in the right half (left = mid + 1). If the left half is not sorted (nums[left] > nums[mid]), then the right half must be. We apply similar logic to search in the right half.
class Solution { public boolean search(int[] nums, int target) { int left = 0; int right = nums.length - 1; while (left <= right) { int mid = left + (right - left) / 2; if (nums[mid] == target) { return true; } // Handle the case of duplicates where we can't decide if (nums[left] == nums[mid] && nums[mid] == nums[right]) { left++; right--; continue; } // Check if the left half is sorted if (nums[left] <= nums[mid]) { // Target is in the sorted left half if (target >= nums[left] && target < nums[mid]) { right = mid - 1; } else { left = mid + 1; } } // Otherwise, the right half must be sorted else { // Target is in the sorted right half if (target > nums[mid] && target <= nums[right]) { left = mid + 1; } else { right = mid - 1; } } } return false; }}Complexity
Time
Average: O(log N), Worst: O(N)
Space
O(1)
Trade-offs
Pros
Much more efficient than linear search on average, with O(log N) time complexity for many cases.
Uses constant extra space.
Cons
The worst-case time complexity degrades to O(N) when the array is filled with duplicates, making it no better than linear search in those specific scenarios.
The logic is more complex to implement and reason about compared to linear search.
Solutions
Solution
class Solution {public boolean search(int[] nums, int target) { int l = 0, r = nums.length - 1; while (l < r) { int mid = (l + r) >> 1; if (nums[mid] > nums[r]) { if (nums[l] <= target && target <= nums[mid]) { r = mid; } else { l = mid + 1; } } else if (nums[mid] < nums[r]) { if (nums[mid] < target && target <= nums[r]) { l = mid + 1; } else { r = mid; } } else { --r; } } return nums[l] == target; }}/** * @param {number[]} nums * @param {number} target * @return {boolean} */ var search = function (nums, target) { let [l, r] = [0, nums.length - 1]; while (l < r) { const mid = (l + r) >> 1; if (nums[mid] > nums[r]) { if (nums[l] <= target && target <= nums[mid]) { r = mid; } else { l = mid + 1; } } else if (nums[mid] < nums[r]) { if (nums[mid] < target && target <= nums[r]) { l = mid + 1; } else { r = mid; } } else { --r; } } return nums[l] === target; };class Solution : def search ( self , nums : List [ int ], target : int ) -> bool : if not nums : return False i = 0 # left pointer j = len ( nums ) - 1 # right pointer while i <= j : mid = ( i + j ) // 2 if nums [ mid ] == target : return True if nums [ i ] <= nums [ mid ]: # left half ordered, right half not ordered if nums [ i ] <= target <= nums [ mid ]: j = mid else : i += 1 else : # right half ordered, left half not ordered if nums [ mid ] <= target <= nums [ j ]: i = mid else : j -= 1 return False ############ class Solution : def search ( self , nums : List [ int ], target : int ) -> bool : l , r = 0 , len ( nums ) - 1 while l <= r : mid = ( l + r ) >> 1 if nums [ mid ] == target : return True if nums [ mid ] < nums [ r ] or nums [ mid ] < nums [ l ]: if target > nums [ mid ] and target <= nums [ r ]: l = mid + 1 else : r = mid - 1 elif nums [ mid ] > nums [ l ] or nums [ mid ] > nums [ r ]: if target < nums [ mid ] and target >= nums [ l ]: r = mid - 1 else : l = mid + 1 else : r -= 1 return Falseclass Solution {public: bool search(vector<int> &nums, int target) { int l = 0, r = nums.size() - 1; while (l < r) { int mid = (l + r) >> 1; if (nums[mid] > nums[r]) { if (nums[l] <= target && target <= nums[mid]) { r = mid; } else { l = mid + 1; } } else if (nums[mid] < nums[r]) { if (nums[mid] < target && target <= nums[r]) { l = mid + 1; } else { r = mid; } } else { --r; } } return nums[l] == target; }};Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.