LeetCode 81: Search in Rotated Sorted Array II

Problem Restatement

We are given an integer array nums.

The array was originally sorted in non-decreasing order, but then rotated at some unknown pivot.

Unlike LeetCode 33, this version may contain duplicate values.

We are also given an integer target.

Return:

True

if target exists in nums.

Otherwise return:

False

The official constraints say 1 <= nums.length <= 5000, -10^4 <= nums[i] <= 10^4, and -10^4 <= target <= 10^4. The array is guaranteed to be rotated at some pivot. The follow-up asks how duplicates affect runtime complexity.

Input and Output

Function shape:

class Solution:
    def search(self, nums: list[int], target: int) -> bool:
        ...

Examples

Example 1:

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

The target 0 appears in the array.

Answer:

True

Example 2:

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

The target 3 does not appear in the array.

Answer:

False

First Thought: Linear Search

The simplest solution is to scan every number.

class Solution:
    def search(self, nums: list[int], target: int) -> bool:
        for num in nums:
            if num == target:
                return True

        return False

This is correct, but it ignores the rotated sorted structure.

Its complexity is:

The problem asks us to decrease the number of operations as much as possible, so we try to adapt binary search.

Key Insight

In a rotated sorted array without duplicates, binary search works because at least one side of the midpoint is clearly sorted.

For example:

nums = [4, 5, 6, 7, 0, 1, 2]

If we look at left, mid, and right, we can usually decide whether the left half or right half is sorted.

With duplicates, this can become ambiguous.

Example:

nums = [1, 0, 1, 1, 1]

At some step, we may see:

nums[left] == nums[mid] == nums[right]

That tells us very little. The pivot could be hidden behind duplicate values.

So the algorithm uses binary search when it can identify a sorted half. When duplicates hide the structure, it safely shrinks the search boundary.

Algorithm

Use two pointers:

left = 0
right = len(nums) - 1

While left <= right:

1. Compute mid.
2. If nums[mid] == target, return True.
3. If nums[left] == nums[mid] == nums[right], shrink both sides.
4. Else if nums[left] <= nums[mid], the left half is sorted.
5. Otherwise, the right half is sorted.
6. Use the sorted half to decide where target can be.
7. If the loop ends, return False.

The duplicate case is the key difference from LeetCode 33:

if nums[left] == nums[mid] == nums[right]:
    left += 1
    right -= 1

This does not skip the target, because we already checked nums[mid]. Also, nums[left] and nums[right] equal nums[mid], so if they were the target, the earlier check would have returned True.

Walkthrough

Use:

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

Start:

left = 0
right = 6
mid = 3
nums[mid] = 0

The middle value equals the target, so return:

True

Now use:

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

Start:

left = 0
right = 6
mid = 3
nums[mid] = 0

0 is not 3.

The right half is sorted because:

nums[mid] <= nums[right]
0 <= 2

The sorted right half is:

[0, 1, 2]

The target 3 is not in that range, so search the left half.

Eventually every possible range is removed, and the algorithm returns:

False

Correctness

The algorithm returns True only when it finds an index mid such that:

nums[mid] == target

So every True result is correct.

Now consider a loop step where the target still exists inside the current search range [left, right].

If nums[left] == nums[mid] == nums[right], the algorithm shrinks both ends. Since nums[mid] was already checked and was not the target, nums[left] and nums[right] also cannot be the target. Removing them preserves the target if it exists.

If the left half is sorted, then every value between nums[left] and nums[mid] lies in sorted order within that half. If target lies inside that value range, the algorithm keeps the left half. Otherwise, the target cannot be in that sorted half, so the algorithm keeps the other half.

The same reasoning applies when the right half is sorted.

Therefore, every pointer update preserves the target whenever the target exists. Since the search range strictly shrinks each iteration, the algorithm eventually finds the target or proves that no valid position remains.

Complexity

Duplicates affect the worst-case runtime. For example:

nums = [1, 1, 1, 1, 1, 1, 1]
target = 2

At many steps, the algorithm cannot identify a sorted half, so it can only shrink the boundary. That degrades the runtime to linear time.

Implementation

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

            if nums[left] == nums[mid] == nums[right]:
                left += 1
                right -= 1

            elif nums[left] <= nums[mid]:
                if nums[left] <= target < nums[mid]:
                    right = mid - 1
                else:
                    left = mid + 1

            else:
                if nums[mid] < target <= nums[right]:
                    left = mid + 1
                else:
                    right = mid - 1

        return False

Code Explanation

We start with the full array:

left = 0
right = len(nums) - 1

The loop runs while there is still a valid search range:

while left <= right:

The midpoint is computed safely:

mid = left + (right - left) // 2

If the midpoint is the target, we are done:

if nums[mid] == target:
    return True

The ambiguous duplicate case is handled first:

if nums[left] == nums[mid] == nums[right]:
    left += 1
    right -= 1

When this happens, binary search cannot tell which side is sorted. Shrinking both sides is safe.

If the left half is sorted:

elif nums[left] <= nums[mid]:

then we check whether the target lies inside that sorted half:

if nums[left] <= target < nums[mid]:
    right = mid - 1
else:
    left = mid + 1

Otherwise, the right half must be sorted:

else:

Then we check whether the target lies inside the sorted right half:

if nums[mid] < target <= nums[right]:
    left = mid + 1
else:
    right = mid - 1

If the loop ends, no position can contain the target:

return False

Testing

def run_tests():
    s = Solution()

    assert s.search([2, 5, 6, 0, 0, 1, 2], 0) is True
    assert s.search([2, 5, 6, 0, 0, 1, 2], 3) is False

    assert s.search([1, 0, 1, 1, 1], 0) is True
    assert s.search([1, 1, 1, 0, 1], 0) is True

    assert s.search([1, 1, 1, 1, 1], 2) is False
    assert s.search([1, 1, 1, 1, 1], 1) is True

    assert s.search([1], 1) is True
    assert s.search([1], 0) is False

    assert s.search([3, 1], 1) is True
    assert s.search([3, 1], 0) is False

    print("all tests passed")

run_tests()

Test meaning: