Search in Rotated Sorted Array II: Handling Duplicates

Search in Rotated Sorted Array II is LeetCode 81, and it is the follow-up to LeetCode 33 that adds one complication: duplicates. The core idea is the same modified binary search you already know. But when nums[lo] == nums[mid] == nums[hi], you lose the ability to determine which half is sorted. That single edge case is the entire difference between this problem and the original.

The problem

You are given an integer array nums sorted in non-decreasing order, then rotated at some unknown pivot. The array may contain duplicates. Given a target, return true if target is in nums, or false otherwise.

Example: nums = [2, 5, 6, 0, 0, 1, 2], target = 0 returns true. target = 3 returns false.

The original sorted array might have been [0, 0, 1, 2, 2, 5, 6]. After rotation, you get [2, 5, 6, 0, 0, 1, 2]. The same two sorted halves exist on either side of the pivot, but now duplicate values can appear at both ends and in the middle.

What changes with duplicates

In the original Search in Rotated Sorted Array (LeetCode 33), the check nums[lo] <= nums[mid] reliably tells you the left half is sorted. That works because all values are unique. If nums[lo] is at most nums[mid], there cannot be a rotation break between them.

With duplicates, that logic breaks down. Consider nums = [1, 0, 1, 1, 1] with target = 0. Here nums[lo] = 1, nums[mid] = 1, and nums[hi] = 1. The left half [1, 0, 1] contains the rotation break but nums[lo] <= nums[mid] is still true. If you trust it and conclude the left half is sorted, you will search the wrong side and miss the target.

The problem is that when all three values are equal, you have zero information about where the sorted half is. The rotation break could be on either side.

Visual walkthrough

First, a simple case: search for target = 0 in [2, 5, 6, 0, 0, 1, 2]. Then the ambiguous case that shows why duplicates require special handling.

The first example finds the target immediately at the midpoint. The second example is the interesting one. With [1, 0, 1, 1, 1], the initial state has nums[lo] == nums[mid] == nums[hi] == 1. You cannot determine which half is sorted, so you shrink both ends. After one shrink, the ambiguity resolves and normal binary search logic takes over.

The code

Here is the complete Python solution for LeetCode 81, Search in Rotated Sorted Array II:

def search(nums, target):
    lo, hi = 0, len(nums) - 1

    while lo <= hi:
        mid = lo + (hi - lo) // 2

        if nums[mid] == target:
            return True

        if nums[lo] == nums[mid] == nums[hi]:
            lo += 1
            hi -= 1
        elif nums[lo] <= nums[mid]:
            if nums[lo] <= target < nums[mid]:
                hi = mid - 1
            else:
                lo = mid + 1
        else:
            if nums[mid] < target <= nums[hi]:
                lo = mid + 1
            else:
                hi = mid - 1

    return False

The structure is almost identical to LeetCode 33. The only addition is the if nums[lo] == nums[mid] == nums[hi] check before the sorted-half logic.

if nums[lo] == nums[mid] == nums[hi]: this is the ambiguity case. You cannot determine which side is sorted, so you shrink both boundaries inward by one. This does not skip any potential matches because you already checked whether nums[mid] == target on the line above.

elif nums[lo] <= nums[mid]: the left half [lo..mid] is sorted. Check if the target falls in the range [nums[lo], nums[mid]). If yes, search left. If no, search right.

else: the right half [mid..hi] is sorted. Check if the target falls in the range (nums[mid], nums[hi]]. If yes, search right. If no, search left.

Why shrinking both ends is safe

When nums[lo] == nums[mid] == nums[hi], you have already confirmed that nums[mid] != target (the target check runs first). Since nums[lo] and nums[hi] have the same value as nums[mid], they also cannot be the target. So incrementing lo and decrementing hi skips only values that definitely do not match.

You are not losing any candidates. You are trimming values that have already been implicitly checked.

Complexity analysis

Time: O(n) worst case, O(log n) average. In the worst case, every element is the same except one (for example, [1, 1, 1, 1, 0, 1, 1, 1]). Each ambiguous step only shrinks the search space by 2, so you end up scanning nearly the entire array. On average, when duplicates are sparse, the algorithm behaves like standard binary search.

Space: O(1). Three variables: lo, hi, mid. No extra data structures.

The O(n) worst case is unavoidable. When all elements look the same, there is no information to halve the search space. Any algorithm for this problem must degrade to O(n) in that scenario.

Edge cases to watch for

• All same elements: nums = [2, 2, 2, 2, 2], target = 3. Every step triggers the ambiguous case. You shrink both ends repeatedly until lo > hi. Returns false. This is the O(n) worst case.
• No rotation: nums = [1, 1, 2, 3, 3]. The left half is always sorted, and the algorithm works like a normal binary search with duplicates.
• Single element: nums = [1]. lo == hi == mid. Check if nums[0] == target and return accordingly.
• Target at the pivot: nums = [3, 4, 5, 1, 2], target = 1. The target sits exactly at the rotation point. The sorted-half check correctly identifies that the target is not in the sorted range, directing the search toward the pivot.

The building blocks

This problem uses two building blocks:

Modified binary search. The same skeleton from LeetCode 33: maintain [lo, hi], compute mid, determine which half is sorted, check if the target is in the sorted range, and eliminate half the search space. If you can write the LeetCode 33 solution from memory, this problem is one extra if statement on top of it.

Ambiguity resolution. When duplicates make the sorted-half check unreliable, you fall back to a linear shrink. This is the new building block. The pattern is simple: if you cannot make a binary decision, reduce the problem size by a constant amount and try again. You see this same idea in other duplicate-handling problems where the non-duplicate version uses a clean binary partition.

# LeetCode 33 (no duplicates):
if nums[lo] <= nums[mid]:
    # left half is sorted

# LeetCode 81 (with duplicates):
if nums[lo] == nums[mid] == nums[hi]:
    lo += 1
    hi -= 1
elif nums[lo] <= nums[mid]:
    # left half is sorted

The only difference is the three-way equality guard at the top. Everything else is identical.

From understanding to recall

You already know how to search in a rotated sorted array from LeetCode 33. This problem adds exactly one new piece: the ambiguity check when nums[lo] == nums[mid] == nums[hi]. That is the only thing you need to drill.

The risk in an interview is not forgetting the core binary search logic. It is forgetting to handle the duplicate edge case at all, or handling it incorrectly (shrinking only one end, or not checking all three values). Spaced repetition locks in that guard clause so you write it automatically.

Type the full solution from scratch today. Tomorrow, type it again. In three days, again. By the third repetition, the if nums[lo] == nums[mid] == nums[hi] line will come out of your fingers before you even think about it.

Related posts

• Search in Rotated Sorted Array (LeetCode 33): Modified Binary Search - The no-duplicates version. Master this first, then LeetCode 81 is one extra guard clause on top
• Find Minimum in Rotated Sorted Array (LeetCode 153) - Uses the same rotated structure but finds the pivot point instead of a target value