Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Search in Rotated Sorted Array II

MEDIUMProblemSolveExternal Links

Description

You are given an integer array nums that was originally sorted in non-decreasing order. The array may contain duplicate values. Before being passed to your function, nums was rotated at an unknown pivot index k (where 0 ≤ k < nums.length). After the rotation, the array becomes:

[nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]

For example, the sorted array [0,1,2,4,4,4,5,6,6,7] might be rotated at pivot index 5 to become [4,5,6,6,7,0,1,2,4,4].

Given this rotated array nums and an integer target, return true if target exists in nums, or false if it does not.

You should try to minimize the number of operations as much as possible.

Important: Unlike the classic "Search in Rotated Sorted Array" problem (where all elements are distinct), this version allows duplicates. This seemingly small difference has a significant impact on how efficiently we can search.

Examples

Example 1

Input: nums = [2,5,6,0,0,1,2], target = 0

Output: true

Explanation: The value 0 appears in the array at index 3 (and also at index 4). Since the target exists in the array, we return true.

Example 2

Input: nums = [2,5,6,0,0,1,2], target = 3

Output: false

Explanation: The value 3 does not appear anywhere in the array. We return false.

Constraints

  • 1 ≤ nums.length ≤ 5000
  • -10^4 ≤ nums[i] ≤ 10^4
  • nums is guaranteed to be rotated at some pivot
  • -10^4 ≤ target ≤ 10^4

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?

Editorial

Brute Force - Linear Scan

Intuition

The simplest way to check if a value exists in an array is to look at every single element, one by one, from left to right. If we find the target, we return true. If we reach the end without finding it, we return false.

This approach completely ignores the fact that the array is sorted (even if rotated). It treats the input as an ordinary, unordered list of numbers. Think of it like searching for a specific book on a shelf by checking every book from left to right — you will definitely find it if it is there, but it might take a while if the shelf is long.

While this approach always works, it does not take advantage of any structure in the data. For an array of 5000 elements, we might end up checking all 5000 of them in the worst case.

Step-by-Step Explanation

Let's trace through nums = [2, 5, 6, 0, 0, 1, 2], target = 0.

Step 1: Start at index 0. The element is 2. Is 2 == 0? No. Move to the next element.

Step 2: Index 1. The element is 5. Is 5 == 0? No. Move to the next element.

Step 3: Index 2. The element is 6. Is 6 == 0? No. Move to the next element.

Step 4: Index 3. The element is 0. Is 0 == 0? Yes! We found the target.

Return true.

We had to check 4 elements before finding the target. In the worst case (target not in array, or target at the very end), we would check all 7 elements.

Linear Scan — Check Every Element — Watch as we scan the array from left to right, comparing each element against the target value 0.

Algorithm

  1. Iterate through the array from index 0 to n-1.
  2. At each index i, compare nums[i] with target.
  3. If nums[i] == target, return true immediately.
  4. If the loop completes without finding the target, return false.

Code

class Solution {
public:
    bool search(vector<int>& nums, int target) {
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] == target) {
                return true;
            }
        }
        return false;
    }
};
class Solution:
    def search(self, nums: list[int], target: int) -> bool:
        for num in nums:
            if num == target:
                return True
        return False
class Solution {
    public boolean search(int[] nums, int target) {
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == target) {
                return true;
            }
        }
        return false;
    }
}

Complexity Analysis

Time Complexity: O(n)

We visit each element at most once, performing a constant-time comparison at each step. In the worst case (target is the last element or not present), we scan the entire array of n elements.

Space Complexity: O(1)

We only use a single loop variable — no extra data structures are needed regardless of the input size.

Why This Approach Is Not Efficient

The linear scan completely ignores a valuable property of the input: the array was sorted before being rotated. A rotated sorted array is made up of two sorted halves. For example, [2, 5, 6, 0, 0, 1, 2] consists of the sorted segment [2, 5, 6] followed by the sorted segment [0, 0, 1, 2].

When an array is sorted, we can use binary search to find an element in O(log n) time instead of O(n). Even though the array is rotated, we can adapt binary search to work here. At each step of binary search, at least one of the two halves (left or right of mid) must be properly sorted. We can check if the target falls within that sorted half and narrow our search accordingly.

The complication with duplicates is that when nums[left] == nums[mid] == nums[right], we cannot determine which half is sorted. In that specific scenario, we must fall back to shrinking the search space by one element from each end. This means the worst case is still O(n) (for example, an array like [1,1,1,1,1,2,1,1,1]), but for most practical inputs with distinct or mostly-distinct values, binary search achieves O(log n) — a significant improvement over always scanning every element.

The key takeaway: while both approaches share the same O(n) worst case, binary search is dramatically faster on average because it skips large portions of the array whenever it can identify a sorted half.

Optimal Approach - Binary Search with Duplicate Handling

Intuition

A rotated sorted array has a special structure: it is composed of two sorted segments joined at the rotation point. For example, [2, 5, 6, | 0, 0, 1, 2] has a left sorted segment [2, 5, 6] and a right sorted segment [0, 0, 1, 2].

In standard binary search on a rotated sorted array (without duplicates), here is the core idea:

  1. Compute mid = (left + right) / 2.
  2. Determine which half (left..mid or mid..right) is sorted.
  3. Check if the target falls within that sorted range.
  4. If yes, search that half. If no, search the other half.

We can tell which half is sorted by comparing nums[left] with nums[mid]:

  • If nums[left] <= nums[mid], the left half is sorted.
  • Otherwise, the right half is sorted.

The duplicate problem: When nums[left] == nums[mid] == nums[right], we cannot tell which half is sorted. Consider these two arrays:

  • [1, 1, 1, 1, 2, 1] — the right half contains the "break"
  • [1, 2, 1, 1, 1, 1] — the left half contains the "break"

Both have nums[left] = nums[mid] = nums[right] = 1, but the sorted half is different! The solution is straightforward: when this ambiguous case occurs, we simply shrink the boundaries by incrementing left and decrementing right. This removes duplicate elements from the edges without losing any information (since we already checked nums[mid] against the target). In the worst case (all elements identical), this degrades to O(n), but on typical inputs with varied values, we still achieve O(log n).

Diagram showing a rotated sorted array with two sorted halves and how binary search identifies which half to search
Diagram showing a rotated sorted array with two sorted halves and how binary search identifies which half to search

Step-by-Step Explanation

Let's trace through nums = [2, 5, 6, 0, 0, 1, 2], target = 1 to see several iterations of binary search including the sorted-half decision logic.

Iteration 1: left=0, right=6, mid=(0+6)/2=3.

  • nums[mid] = nums[3] = 0. Is 0 == 1? No.
  • Check for duplicate ambiguity: nums[left]=2, nums[mid]=0, nums[right]=2. All three equal? No (2 ≠ 0). No ambiguity.
  • Is the left half sorted? nums[left]=2 ≤ nums[mid]=0? No (2 > 0). So the left half is NOT sorted, meaning the right half [0,0,1,2] must be sorted.
  • Is target=1 in the sorted right half? Check: nums[mid] < 1 ≤ nums[right]? 0 < 1 and 1 ≤ 2? Yes! Search right: set left = mid + 1 = 4.

Iteration 2: left=4, right=6, mid=(4+6)/2=5.

  • nums[mid] = nums[5] = 1. Is 1 == 1? YES! Target found!

Return true.

Binary search found the target in just 2 iterations, compared to 6 comparisons a linear scan would need to reach index 5.

Now let's also trace nums = [2, 5, 6, 0, 0, 1, 2], target = 3 (a case where the target does not exist) to see more iterations:

Iteration 1: left=0, right=6, mid=3. nums[3]=0 ≠ 3.

  • Left sorted? 2 ≤ 0? No → right half is sorted.
  • Target=3 in right half? 0 < 3 ≤ 2? No (3 > 2). Target is NOT in the sorted right half.
  • Search left: right = mid - 1 = 2.

Iteration 2: left=0, right=2, mid=1. nums[1]=5 ≠ 3.

  • Left sorted? nums[0]=2 ≤ nums[1]=5? Yes → left half [2,5] is sorted.
  • Target=3 in left half? 2 ≤ 3 < 5? Yes! Search left: right = mid - 1 = 0.

Iteration 3: left=0, right=0, mid=0. nums[0]=2 ≠ 3.

  • Left sorted? 2 ≤ 2? Yes. Target=3 in [2..2]? 2 ≤ 3 < 2? No. Search right: left = 1.

Now left=1 > right=0. Loop ends. Return false.

Binary Search with Duplicate Handling — Finding Target in Rotated Sorted Array — Watch how binary search identifies the sorted half at each step and narrows the search space, with special handling when duplicates create ambiguity.

Algorithm

  1. Initialize left = 0 and right = nums.length - 1.
  2. While left ≤ right:
    a. Compute mid = left + (right - left) / 2.
    b. If nums[mid] == target, return true.
    c. Handle duplicates: If nums[left] == nums[mid] and nums[mid] == nums[right], we cannot determine which half is sorted. Increment left by 1 and decrement right by 1, then continue to the next iteration.
    d. Left half is sorted (if nums[left] ≤ nums[mid]):
    • If nums[left] ≤ target < nums[mid], the target is in the left half → set right = mid - 1.
    • Otherwise, search the right half → set left = mid + 1.
      e. Right half is sorted (otherwise):
    • If nums[mid] < target ≤ nums[right], the target is in the right half → set left = mid + 1.
    • Otherwise, search the left half → set right = mid - 1.
  3. If the loop ends without finding the target, return false.

Code

class Solution {
public:
    bool search(vector<int>& nums, int target) {
        int left = 0;
        int right = nums.size() - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2;

            if (nums[mid] == target) {
                return true;
            }

            // Handle the ambiguous duplicate case
            if (nums[left] == nums[mid] && nums[mid] == nums[right]) {
                left++;
                right--;
                continue;
            }

            // Left half is sorted
            if (nums[left] <= nums[mid]) {
                if (nums[left] <= target && target < nums[mid]) {
                    right = mid - 1;  // target is in sorted left half
                } else {
                    left = mid + 1;   // target is in right half
                }
            }
            // Right half is sorted
            else {
                if (nums[mid] < target && target <= nums[right]) {
                    left = mid + 1;   // target is in sorted right half
                } else {
                    right = mid - 1;  // target is in left half
                }
            }
        }

        return false;
    }
};
class Solution:
    def search(self, nums: list[int], target: int) -> bool:
        left = 0
        right = len(nums) - 1

        while left <= right:
            mid = left + (right - left) // 2

            if nums[mid] == target:
                return True

            # Handle the ambiguous duplicate case
            if nums[left] == nums[mid] == nums[right]:
                left += 1
                right -= 1
                continue

            # Left half is sorted
            if nums[left] <= nums[mid]:
                if nums[left] <= target < nums[mid]:
                    right = mid - 1  # target is in sorted left half
                else:
                    left = mid + 1   # target is in right half
            # Right half is sorted
            else:
                if nums[mid] < target <= nums[right]:
                    left = mid + 1   # target is in sorted right half
                else:
                    right = mid - 1  # target is in left half

        return False
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 ambiguous duplicate case
            if (nums[left] == nums[mid] && nums[mid] == nums[right]) {
                left++;
                right--;
                continue;
            }

            // Left half is sorted
            if (nums[left] <= nums[mid]) {
                if (nums[left] <= target && target < nums[mid]) {
                    right = mid - 1;  // target is in sorted left half
                } else {
                    left = mid + 1;   // target is in right half
                }
            }
            // Right half is sorted
            else {
                if (nums[mid] < target && target <= nums[right]) {
                    left = mid + 1;   // target is in sorted right half
                } else {
                    right = mid - 1;  // target is in left half
                }
            }
        }

        return false;
    }
}

Complexity Analysis

Time Complexity: O(log n) average, O(n) worst case

In the average case, binary search eliminates half the search space at each iteration, giving O(log n) time. However, when the array contains many duplicates and we hit the ambiguous case (nums[left] == nums[mid] == nums[right]), we can only shrink the search space by 2 elements (one from each end). In the worst case — for example, nums = [1,1,1,1,1,2,1,1,1] with target=2 — we might shrink one element at a time through most of the array, resulting in O(n) time. This worst case is unavoidable: with duplicates, there is no way to determine which half contains the pivot without checking.

Space Complexity: O(1)

We use only a fixed number of variables (left, right, mid) regardless of the input size. No recursion or auxiliary data structures are needed.

Comparison with Brute Force:

ApproachAverage CaseWorst CaseSpace
Linear ScanO(n)O(n)O(1)
Binary Search (with duplicates)O(log n)O(n)O(1)

While the worst case is the same, the average case of binary search is exponentially faster. For an array of 5000 elements, binary search typically needs about 12-13 comparisons versus up to 5000 for linear scan.