Given a sorted integer array nums that has been rotated at an unknown pivot, and an integer target, return true if target is in nums, or false if it is not.
Note: The array may contain duplicates.
Prerequisite: Search in a Rotated Sorted Array 1
Example 1
Input: nums = [2, 5, 6, 0, 0, 1, 2], target = 0
Output: true
Explanation: The target value 0 is present in the array at index 3 and index 4. Therefore, the function returns true.
Example 2
Input: nums = [2, 5, 6, 0, 0, 1, 2], target = 3
Output: false
Explanation: The target value 3 is not present anywhere in the array. Therefore, the function returns false.
Brute Force Approach
The most straightforward way to find an element in any collection is to check every single item one by one. We do not need to worry about whether the array is sorted, rotated, or contains duplicates because a complete scan will always find the target if it exists.
This approach works universally because it covers the entire search space. We start from the first element and move towards the last element, making a simple decision at each step: does the current element equal our target?
Algorithm
Start a loop from the first index (0) up to the last index (N - 1) and check each index.
At each index, compare the current element with the target.
If they match, immediately stop and return true , we have found the number.
If the loop finishes without finding a match, return false.
Dry Run
Search in a Rotated Sorted Array 2 Brute Dry Run
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: /* Checks whether the target exists anywhere in the rotated array. */ bool search(vector<int>& nums, int target) { // Check every value from left to right. for (int i = 0; i < (int)nums.size(); i++) { // Return true as soon as the target is found. if (nums[i] == target) { return true; } } return false; }};// Driver code startsint main() { vector<int> nums = {2, 5, 6, 0, 0, 1, 2}; int target = 0; Solution obj; cout << (obj.search(nums, target) ? "true" : "false") << endl; return 0;}Complexity Analysis
Time Complexity: O(N), N is the size of array, because the whole array may need to be scanned.
Space Complexity: O(1), because only a loop variable is used.
Optimal Approach
Search in Rotated Sorted Array 2 is almost the same as Search in a Rotated Sorted Array 1. The same binary-search observation still applies: around mid, at least one half is sorted.
If the left half is sorted, check whether target lies in the range [low, mid]. If yes, search the left half; otherwise, search the right half. Similarly, if the right half is sorted, check whether target lies in the range [mid, high].
The only extra edge case comes from duplicates:
nums[low] == nums[mid] && nums[mid] == nums[high]Duplicates don't break the sorted-half observation; duplicates can make identifying the sorted half impossible.
So in such a case, shrink the search space by doing low++ and high--, then continue binary search.
Algorithm
Start with
low = 0andhigh = N - 1.While
low <= high, findmid = low + (high - low) / 2.If
nums[mid] == target, returntrue.If
nums[low] == nums[mid] && nums[mid] == nums[high]:Increase
lowby1.Decrease
highby1.Continue.
Otherwise, check whether the left half is sorted using
nums[low] <= nums[mid].If the left half is sorted:
If
targetlies betweennums[low]andnums[mid], movehigh = mid - 1.Otherwise, move
low = mid + 1.
Else, the right half must be sorted:
If
targetlies betweennums[mid]andnums[high], movelow = mid + 1.Otherwise, move
high = mid - 1.
If the loop ends, return
false.
Key Points
When
nums[low] == nums[mid] == nums[high], the sorted half cannot be identified safely, so shrinking both ends is the correct move.In the worst case, such as many repeated values, the time complexity can degrade to
O(N).
Dry Run
Search in Rotated Sorted Array - 2 Optimal
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: /* Checks whether the target exists anywhere in the rotated array. */ bool search(vector<int>& nums, int target) { // Left boundary of the current search range. int low = 0; // Right boundary of the current search range. int high = (int)nums.size() - 1; // Keep searching while a valid range still exists. while (low <= high) { // Calculate the middle index safely. int mid = low + (high - low) / 2; // The target is found at the middle position. if (nums[mid] == target) { return true; } // Duplicates at both ends hide which half is sorted. if (nums[low] == nums[mid] && nums[mid] == nums[high]) { low++; high--; } // The left half is normally sorted. else if (nums[low] <= nums[mid]) { // The target lies inside the sorted left half. if (nums[low] <= target && target < nums[mid]) { high = mid - 1; } else { // The target must lie in the other half. low = mid + 1; } } else { // The right half must be normally sorted here. if (nums[mid] < target && target <= nums[high]) { low = mid + 1; } else { // The target must lie in the other half. high = mid - 1; } } } return false; }};// Driver code startsint main() { vector<int> nums = {2, 5, 6, 0, 0, 1, 2}; int target = 0; Solution obj; cout << (obj.search(nums, target) ? "true" : "false") << endl; return 0;}Complexity Analysis
Time Complexity: Average case is close to O(log N), but the worst case becomes O(N) because duplicate-heavy cases may force the search range to shrink one step at a time. N is the size of array.
Space Complexity: O(1), because only a few variables are used.
Interview follow-up Questions
When nums[low] == nums[mid] == nums[high], it is impossible to determine which half of the array is sorted. We are forced to reduce our search space linearly by moving pointers inward by one step, which can take O(N) operations if all elements are identical.
Be the first to add a comment.