Workspace

Problem workspace

3 day streakD

Rotated Search with Duplicates

MediumBinary SearchRotations & structure

The challenge

Find any matching target index in a rotated nondecreasing array, or return −1.

Duplicates allowed. Any matching index is valid; empty input returns −1.

Example

[1, 0, 1, 1, 1], target = 0 → 1.

Use the walkthrough below to inspect the input and each state change.

See Duplicate-aware rotation, step by step

Inspect the comparison, the invariant, and the next boundary.

Inclusive candidate indicestarget = 0
L = 0 · mid = — · R = 41001121314
Current comparisonResolved positionNumbers below = indices
Left
0
Middle
—
Right
4
Step 01 / 5

Start with the candidate indices

The retained interval contains the answer whenever it exists. Watch why each comparison can discard one side.

left = 0; right = 4

Recorded result so far

Not resolved
View exact input

Input: [1,0,1,1,1] · target = 0

Put it into code

Use rotated search, but remove both endpoints when left, middle, and right all have the same value after a failed equality check.

Indices are zero-based. C++ uses C++17 or later.

def rotated_search(nums, target):
    left, right = 0, len(nums) - 1
    while left <= right:
        mid = left + (right - left) // 2
        if nums[mid] == target:
            return mid
        if nums[left] == nums[mid] == nums[right]:
            left += 1
            right -= 1
            continue
        if 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 -1

A good place to start

Explore a pattern

A little guidance

Start with a pattern, read through a problem, and mark it solved when the idea clicks. Save anything you want to revisit.

New tutorials are added one at a time. Your bookmarks and solved checkmarks stay in this browser.

Explore the roadmap