Search in Rotated Sorted Array II — Solution

Problem

A sorted array can be "rotated" by shifting some prefix of elements to the back. Given such a rotated array that may contain duplicate values, determine whether a given target appears in it.

• Input: nums = [2,5,6,0,0,1,2], target = 0
• Output: true
• Explanation: 0 appears at indices 3 and 4.

Counter-example: nums = [2,5,6,0,0,1,2], target = 3 → false. Even though the array contains values around 3, the value 3 itself is absent.

Intuition

The array is two sorted runs glued together at a rotation point. Binary search normally works by identifying which half is sorted, then ruling out the other. Duplicates break this: when the leftmost, middle, and rightmost values are all equal, you cannot tell which side the rotation sits on. The only safe move in that case is to shrink both ends by one and try again — which is why worst-case performance degrades to O(n) when all elements are identical.

Approach 1 — Linear Scan

Scan every element once. Return true on the first match, false if the loop finishes without finding the target.

1. Iterate through each element in nums.
2. Return true if the current element equals target.
3. Return false after exhausting the array.

1def search(nums: list[int], target: int) -> bool:
2    for value in nums:
3        if value == target:
4            return True
5    return False

Time: O(n) — every element may be visited in the worst case.
Space: O(1) — no extra memory used.

Approach 2 — Modified Binary Search

Use binary search but add a dedicated branch for the ambiguous duplicate case: when the left, mid, and right values are all equal, shrink both ends simultaneously and continue.

1. Set left = 0, right = len(nums) - 1.
2. While left <= right, compute mid.
3. If nums[mid] == target, return true.
4. If nums[left] == nums[mid] == nums[right], shrink both ends (left++, right--) — we cannot determine the sorted half.
5. If nums[left] <= nums[mid], the left half [left..mid] is sorted: if target falls in [nums[left], nums[mid]), move right = mid - 1; otherwise left = mid + 1.
6. Otherwise the right half [mid..right] is sorted: if target falls in (nums[mid], nums[right]], move left = mid + 1; otherwise right = mid - 1.
7. Return false when the window collapses without a match.

1def search(nums: list[int], target: int) -> bool:
2    left, right = 0, len(nums) - 1
3
4    while left <= right:
5        mid = (left + right) // 2
6
7        if nums[mid] == target:
8            return True
9
10        # Cannot determine which half is sorted — shrink both ends safely
11        if nums[left] == nums[mid] == nums[right]:
12            left += 1
13            right -= 1
14        elif nums[left] <= nums[mid]:  # left half [left..mid] is the sorted portion
15            if nums[left] <= target < nums[mid]:
16                right = mid - 1  # target must lie in the sorted left half
17            else:
18                left = mid + 1   # target lies in the right half
19        else:  # right half [mid..right] is the sorted portion
20            if nums[mid] < target <= nums[right]:
21                left = mid + 1   # target must lie in the sorted right half
22            else:
23                right = mid - 1  # target lies in the left half
24
25    return False

Time: O(log n) average — degrades to O(n) only when all elements are identical.
Space: O(1) — only a constant number of index variables.

Complexity Summary

Common Mistakes

• Applying the no-duplicates version directly — in Search in Rotated Sorted Array I, nums[left] <= nums[mid] reliably identifies the sorted half. With duplicates, this is false when nums[left] == nums[mid] but the rotation sits inside the left half; you must check all three endpoints before committing to a side.
• Shrinking only one end when ambiguous — when all three endpoints match, skipping only left++ leaves the right boundary stale, which can incorrectly prune the right half in the next iteration. Both ends must shrink symmetrically.
• Getting the range-check inequalities wrong — the left-half check must be nums[left] <= target < nums[mid] (strict on the right), and the right-half check must be nums[mid] < target <= nums[right] (strict on the left), because nums[mid] itself was already tested at the top of the loop.
• Using strict < for the sorted-half condition — the condition nums[left] <= nums[mid] must use <= because when left == mid (a single-element window), strict < would falsely route to the right-half branch.
• Assuming O(n) worst case disqualifies binary search — the degraded O(n) case only occurs when every element is identical, which is trivially detectable beforehand; for typical interview inputs the binary search runs in O(log n).

Related Problems

• Search in Rotated Sorted Array — the no-duplicates variant where binary search is always O(log n)
• Find Minimum in Rotated Sorted Array — locating the rotation pivot using the same sorted-half identification technique
• Binary Search — the foundational template that all rotated-array variants extend
• Find First and Last Position of Element in Sorted Array — binary search over duplicates to find exact left and right boundaries
• Single Element in a Sorted Array — uses index parity to identify which half holds the answer, a similar "which side is normal?" reasoning pattern