Search in Rotated Sorted Array II

Duplicates turn a clean binary-search decision into an information problem. When nums[left], nums[mid], and nums[right] are equal, you cannot tell which side contains the rotation. The safe move is to remove only redundant evidence, not guess.

The solution direction is:

1. Check nums[mid].
2. If the boundary comparisons identify a sorted half, use its value range to discard the impossible half.
3. If duplicates make the orientation ambiguous, contract the interval by one redundant boundary.
4. Preserve the invariant that every possible occurrence of target remains inside the active interval.

That is the core of a correct Search in Rotated Sorted Array II solution.

The duplicate case breaks the usual shortcut

The array was originally sorted in non-decreasing order, then rotated at an unknown pivot. Duplicate values are allowed, and the function returns only whether target is present.

For example:

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

The target exists, so the answer is True.

With distinct values, the usual rotated-search rule works neatly: inspect mid, determine which half is sorted, and decide whether the target belongs in that half. At least one side gives you enough information to eliminate half the interval.

Duplicates can erase that signal.

Consider:

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

Suppose:

left = 0
mid = 2
right = 4

Then:

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

The values at all three decision points are equal. The rotation could be hiding on either side of mid, and the comparisons do not tell us which half is ordered in a useful way.

This is the central modification:

When comparisons prove a sorted half, eliminate aggressively. When duplicates destroy that proof, make only a safe one-step reduction.

Start with the simple baseline

A direct scan solves the problem:

for value in nums:
    if value == target:
        return True
return False

That takes O(n) time and O(1) extra space. It is correct and easy to verify, but it ignores the array's ordering.

The optimized approach still uses a closed candidate interval:

[left, right]

At every iteration, left, mid, and right describe the entire state needed for a presence query. There is no need to find the rotation pivot first. Pivot extraction adds another task and does not solve the duplicate ambiguity.

The goal is repeated elimination:

• remove half the interval when the ordering proves that half impossible;
• remove one boundary when duplicates prevent a half-interval proof.

That second case matters. Modified binary search is not automatically logarithmic. If the data hides the ordering signal, the algorithm must trade speed for certainty.

Derive the three-way decision

Use a closed interval and continue while left <= right.

mid = (left + right) // 2

There are three meaningful comparisons.

1. The midpoint is the target

This is always the first check:

if nums[mid] == target:
    return True

It also matters for the ambiguity case. Once nums[mid] has been checked and rejected, an equal boundary can be removed safely because it carries no new information about a target occurrence.

2. nums[mid] > nums[right]: the left side is ordered

If:

nums[mid] > nums[right]

then the interval crosses the rotation between mid and right. The segment from left through mid is sorted:

nums[left] <= ... <= nums[mid]

Now test whether the target could lie in that sorted range.

Because nums[mid] == target was already handled, the practical test can use:

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

If the target falls inside the sorted left range, keep that range. Otherwise, discard it and search the right side.

The inclusive lower bound matters. If target == nums[left], the left endpoint may be the answer and must remain eligible.

3. nums[mid] < nums[right]: the right side is ordered

If:

nums[mid] < nums[right]

then the segment from mid through right is sorted:

nums[mid] <= ... <= nums[right]

Test the target against that range:

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

Again, nums[mid] == target was already handled, so the lower comparison can be strict. The upper bound remains inclusive because target == nums[right] is a valid endpoint match.

4. nums[mid] == nums[right]: the ordering is ambiguous

This is the duplicate-specific branch:

right -= 1

Why is this safe?

• nums[mid] was already checked and is not the target.
• nums[right] == nums[mid], so nums[right] has the same rejected value.
• Removing right cannot remove the only occurrence of target.

We do not claim to know which side is sorted. We simply remove an endpoint that adds no distinguishing information.

The decision table looks like this:

Condition	What it proves	Safe update
nums[mid] == target	The target is present	Return True
nums[mid] > nums[right]	left..mid is sorted	Use its value range
nums[mid] < nums[right]	mid..right is sorted	Use its value range
nums[mid] == nums[right]	The boundary comparison is inconclusive	Decrement right

The important distinction is between proof and guessing. Strict comparisons prove a sorted side. Equality does not.

Protect the shrinking-interval invariant

The correctness argument should be visible before the code.

At the start of every iteration, if target occurs anywhere in nums, at least one occurrence remains inside the closed interval [left, right].

Every boundary update must preserve that statement.

Sorted-left branch

Suppose:

nums[mid] > nums[right]

Then nums[left..mid] is sorted.

If:

nums[left] <= target < nums[mid]

the target may be in the left sorted portion, so we set:

right = mid - 1

The midpoint was already checked and is not the target. The remaining interval still contains every possible occurrence.

Otherwise, the target is either smaller than nums[left] or greater than nums[mid]. Since nums[left..mid] is sorted, it cannot occur there. We discard it:

left = mid + 1

Sorted-right branch

Suppose:

nums[mid] < nums[right]

Then nums[mid..right] is sorted.

If:

nums[mid] < target <= nums[right]

the target may be in that right sorted portion, so we move:

left = mid + 1

Again, mid was already checked.

Otherwise, the target cannot occur in the sorted right portion, so we discard it:

right = mid - 1

Ambiguous branch

Suppose:

nums[mid] == nums[right]

The midpoint is not the target. The right endpoint has the same value as the rejected midpoint. Removing it cannot remove a target occurrence:

right -= 1

This branch may remove only one element, but it still makes strict progress. The interval cannot remain unchanged.

That gives us two correctness obligations:

1. Candidate preservation: never discard a region that could contain the target.
2. Progress: every branch moves left forward or right backward.

When the loop exits, left > right. The candidate interval is empty, so no occurrence remains. Returning False is then justified.

Trace the ambiguity by hand

Use the duplicate-heavy array:

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

A trace with a closed interval:

left	mid	right	Compared values	Branch	Remaining interval
0	2	4	1, 1, 1	Ambiguous: nums[mid] == nums[right]	[0, 3]
0	1	3	1, 1, 0	Left side is sorted; target is not in [1, 1]	[2, 3]
2	2	3	1, 1, 0	Left side is sorted; target is not in [1, 1]	[3, 3]
3	3	3	0	Midpoint matches	True

The first iteration cannot eliminate half the array. The equal 1s act like fog around the pivot. We peel one endpoint, then the strict comparison reveals enough structure to discard a larger region.

Now compare that with the canonical example:

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

Initially:

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

The midpoint matches immediately.

For an absent target, such as target = 3, the same state machine continues until the candidate interval becomes empty. The algorithm does not need a separate “target absent” strategy. Absence is the result of exhausting every interval that the invariant allowed us to keep.

Implement the proof in Python

Here is an interview-ready implementation using a closed interval:

def search(nums: list[int], target: int) -> bool:
    left, right = 0, len(nums) - 1

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

        if nums[mid] == target:
            return True

        if nums[mid] > nums[right]:
            # nums[left..mid] is sorted.
            if nums[left] <= target < nums[mid]:
                right = mid - 1
            else:
                left = mid + 1

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

        else:
            # nums[mid] == nums[right].
            # The midpoint was checked, so this endpoint is redundant.
            right -= 1

    return False

Each variable has a direct obligation:

• left and right define the current candidate interval.
• mid is the element being tested.
• The first comparison checks the actual answer.
• The next two branches use proven ordering.
• The final branch removes only duplicate information.

I prefer this version in an interview because the control flow mirrors the derivation. A shorter implementation is not automatically better if it hides why a boundary update is safe.

Implementation checklist

Before submitting, verify:

• The interval convention is consistently closed: left <= right.
• A midpoint match returns immediately.
• The sorted-half tests use the correct endpoint inclusivity.
• The ambiguity branch always shrinks the interval.
• No branch can leave left and right unchanged.
• Targets equal to nums[left] or nums[right] remain eligible.
• The function returns False only after the candidate interval is empty.

Avoid these tempting detours:

• Finding the pivot first: unnecessary for a boolean presence query.
• Sorting again: destroys the point of using the existing structure.
• Slicing subarrays: adds allocation and obscures the interval invariant.
• Converting to a set: may give expected constant-time lookup, but it discards the intended space constraint and the ordering lesson.

Complexity and edge-case audit

When the comparisons identify a sorted half, the interval is cut substantially, giving the familiar O(log n) behavior.

Duplicates change the worst case. If repeated iterations satisfy:

nums[mid] == nums[right]

the algorithm may reduce the interval by only one element per iteration. In that case, the runtime degrades to:

O(n)

The extra space remains:

O(1)

This degradation is structural, not an implementation failure. Equal values can conceal the rotation, and no safe comparison lets us discard half the interval. The algorithm cannot manufacture information that the input does not expose.

Test cases should target the places where a plausible implementation lies:

cases = [
    ([1], 1),                    # singleton, present
    ([1], 2),                    # singleton, absent
    ([1, 1, 1, 1], 1),           # all equal, present
    ([1, 1, 1, 1], 2),           # all equal, absent
    ([1, 2, 3, 4], 1),           # effectively unrotated
    ([1, 2, 3, 4], 4),           # right endpoint
    ([1, 2, 3, 4], 0),           # absent target
    ([2, 5, 6, 0, 0, 1, 2], 0),  # canonical present case
    ([2, 5, 6, 0, 0, 1, 2], 3),  # canonical absent case
    ([1, 1, 1, 0, 1], 0),        # ambiguity around the pivot
    ([1, 0, 1, 1, 1], 0),        # duplicate values on the other side
]

Pay particular attention to:

• target at the left boundary;
• target at the right boundary;
• rotation near either end;
• duplicates straddling the pivot;
• all values equal;
• an absent target that falls numerically between existing values.

The failure mode to hunt is premature elimination. If you use strict inequalities at both ends without checking the boundary contract, you can discard a valid endpoint. If you classify a half when its ordering was not actually proved, you can discard the target itself.

The transferable pattern

Rotated-array search is a lesson in evidence.

When comparisons prove a sorted side, use that structure to eliminate the impossible range. When duplicates erase the proof, do less—but do it safely. Contract the interval only by evidence that is definitely redundant.

The reusable rule is:

Prove a sorted side when the data allows it. When duplicates hide the side, protect the candidate interval and take only a safe reduction.

That is the difference between a binary-search solution that merely resembles the pattern and one that survives the input that breaks the pattern.