Search in Rotated Sorted Array II

You are given an integer array nums that was originally sorted in non-decreasing order — but it may contain duplicate values. Before it reaches you, the array is rotated at some unknown pivot index k (0 <= k < nums.length), so it becomes [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]].

For example, [0,1,2,4,4,4,5,6,6,7] rotated at pivot index 5 becomes [4,5,6,6,7,0,1,2,4,4].

Given the rotated array nums and an integer target, return true if target exists in nums, and false otherwise.

A plain linear scan works — but the interviewer wants you to decrease the overall number of operation steps as much as possible. Can you exploit the leftover sorted structure, and can you explain exactly where duplicates hurt you?

Hints

· Stuck? Reveal one nudge at a time.

If the array had no duplicates, one comparison between nums[lo] and nums[mid] would tell you which half is sorted. What could go wrong with that comparison here?

When nums[lo], nums[mid], and nums[hi] are all equal, the comparison carries no information — the target could hide in either half. You cannot discard half the array.

In that all-equal case, you have already checked nums[mid] against the target — so nums[lo] and nums[hi] cannot be the target either. Shrink both ends by one and retry; otherwise binary-search the sorted half exactly like the classic rotated-array search.

Common doubts

Consider an array of 4999 copies of 1 hiding a single 2, with target = 2. Every probe sees nums[lo] == nums[mid] == nums[hi], so each step can only shrink the range by two — and no algorithm can do better, because the 2 could be at any unexamined position. Duplicates destroy the guarantee, not just this particular algorithm.

With duplicates, target may appear many times, so which index to return is ambiguous. Existence is the natural question. (Returning the first occurrence is a good follow-up — it combines this technique with a lower-bound search.)

No. The shrink only fires after nums[mid] != target is confirmed, and it only fires when nums[lo] and nums[hi] equal nums[mid]. Values already ruled out as the target are always safe to drop.

Yes. A pivot of 0 reproduces the sorted array, in which case nums[lo] <= nums[mid] always holds and the algorithm behaves as plain binary search on the left-sorted branch.

Interview follow-ups

· What an interviewer asks next.

First locate the pivot (minimum) with a duplicate-tolerant binary search, then run a lower-bound binary search on the logical sorted order using index arithmetic modulo n — or simpler, binary-search each of the two sorted segments for the leftmost occurrence. Same O(log n) average, O(n) worst.

The same tie-breaking idea: compare nums[mid] with nums[hi]; when they are equal you cannot tell which side holds the minimum, so decrement hi by one. That is exactly Find Minimum in Rotated Sorted Array II.

No. An adversary argument settles it: in an array of identical values with at most one different element, any unexamined position could hold the target, so every comparison-based algorithm must inspect Ω(n) elements in the worst case.

Fun facts

The one-line difference from the duplicate-free version — shrink both ends on a three-way tie — is enough to change the provable worst case from O(log n) to O(n). Few problems show so crisply how a small change in input guarantees reshapes complexity.
The safe-to-shrink argument (equal values already ruled out cannot be the answer) is the same trick that powers Find Minimum in Rotated Sorted Array II and several duplicate-tolerant two-pointer problems.
Interviewers love the follow-up question about complexity here: stating 'O(log n) average, O(n) worst — and here is the adversarial input' before being asked is a strong senior signal.

Asked at

AmazonMicrosoftGoogleBloombergAdobe

Frequently Sometimes Occasionally

Example 1

Input: nums = [2,5,6,0,0,1,2], target = 0
Output: true
The sorted array [0,0,1,2,2,5,6] was rotated to [2,5,6,0,0,1,2]; 0 appears in it.

Example 2

Input: nums = [2,5,6,0,0,1,2], target = 3
Output: false
3 does not appear anywhere in the array.

Constraints

- 1 <= nums.length <= 5000 - -10^4 <= nums[i] <= 10^4 - nums is guaranteed to be rotated at some pivot (possibly pivot 0, leaving it fully sorted) - -10^4 <= target <= 10^4

This problem is the sequel to Search in Rotated Sorted Array — same rotated shelf, one cruel twist: duplicates. That single change breaks a core assumption of the classic solution and teaches you one of binary search's most instructive edge cases: what to do when comparisons stop giving you information.

Prerequisites

Before you start

· Concepts used directly in the solution.

Binary search. Halving a search range with lo, hi, and mid pointers until it collapses.

Rotated sorted arrays. A sorted array cut at a pivot and glued in swapped order — at every mid, at least one half is still sorted.

Worst-case vs average-case analysis. Why the same algorithm can be O(log n) on typical inputs yet O(n) on adversarial ones.

Understand the problem

Plain English: the array is a sorted list that got rotated, possibly with repeats. Report whether target is in it — a yes/no answer, not an index (with duplicates, which index would be ambiguous anyway).

Formally: given nums, a non-decreasing array rotated at some pivot k, and an integer target, return true iff some i satisfies nums[i] == target.

Worked example — nums = [2,5,6,0,0,1,2], target = 0

sorted original : [0, 0, 1, 2, 2, 5, 6]
rotated (k = 3) : [2, 5, 6, 0, 0, 1, 2]
                   └─ larger tail ─┘└ wrapped smaller head

0 appears (twice, even) → true

Clarifying questions

Asking two or three sharp questions before coding shows you have solved the classic version and know exactly what changed.

Questions to ask first

· Signals seniority before you write a line of code.

Input guarantees

“Can the array contain duplicate values?”

Yes — this is the whole problem. With duplicates, comparing the ends to the middle can be inconclusive, and the guaranteed logarithmic bound is lost.

“Is a rotation of zero positions possible, leaving the array fully sorted?”

Yes. Pivot k = 0 reproduces the original array, so your logic must handle a plain sorted array too — classic rotated-search code already does.

Output shape

“Do I return an index or just whether the target exists?”

Just a boolean. Duplicates make the index ambiguous, so the problem only asks for existence.

Constraints and scale

“How large can the array be?”

Up to 5000 elements — small enough that O(n) passes, so the real test is whether you can articulate the O(log n) average approach and why the worst case degrades.

The ideal opening — say it like this

Before I code, let me confirm the key difference from the classic rotated-array search: duplicates are allowed here, correct?

Since duplicates make the answer index ambiguous, I will return a boolean for existence rather than a position.

I will binary-search the sorted half as usual, and when the endpoints equal the middle I will shrink both ends by one — which is why the worst case degrades from logarithmic to linear.

Key observations

1Aha

At every mid, at least one half of a rotated array is sorted

Cut a rotated sorted array anywhere: the rotation point falls on one side of mid, so the other side is a clean ascending run. If nums[lo] <= nums[mid], the left half [lo..mid] is sorted; otherwise the right half [mid..hi] is. Once you know which half is sorted, one range check — is target inside that half's endpoints? — tells you which half to keep.

[2, 5, 6, 0, 0, 1, 2]   lo=0, mid=3, hi=6
 └─sorted?─┘
 nums[lo]=2 > nums[mid]=0 → left is NOT sorted → right half [0,0,1,2] is

2Aha

Duplicates can make both halves look identical

The rule above needs nums[lo] <= nums[mid] to mean something. Consider [1, 0, 1, 1, 1] with mid = 2: here nums[lo] == nums[mid] == nums[hi] == 1. The left half looks sorted (1 <= 1) but is not — 0 hides inside it. When all three probes are equal, the comparison carries zero information: the target could be hiding in either half.

3Aha

When the probes tie, shrinking both ends is safe

Suppose nums[lo] == nums[mid] == nums[hi] and we already checked nums[mid] != target. Then nums[lo] != target and nums[hi] != target either — so discarding one element from each end (lo++, hi--) can never throw away the target. It only costs progress: each tie shrinks the range by 2 instead of halving it. That is precisely why an adversarial input like [1,1,1,1,...,1] hiding a single 2 forces O(n) — no algorithm can beat that, because any unexamined position could hold the answer.

Brute force vs optimal

	Brute force	Optimal
Time	O(n) always	O(log n) average, O(n) worst
Space	O(1)	O(1)
Idea	Scan every element	Binary search the sorted half; shrink both ends on ties

Full, runnable code for both approaches lives in the Approaches selector below.

Summary

Key takeaway

Rotated-array binary search survives duplicates with one extra rule: when nums[lo] == nums[mid] == nums[hi], shrink both ends and retry — the comparison gave no information, and equal, already-rejected values are safe to drop. The pattern degrade gracefully when a probe is inconclusive reappears in Find Minimum in Rotated Sorted Array II.

lo, hi = 0, n-1
while lo <= hi:
    mid = (lo + hi) / 2
    if nums[mid] == target: return true
    if nums[lo] == nums[mid] == nums[hi]: lo++, hi--      # tie: no info
    else if nums[lo] <= nums[mid]:                        # left half sorted
        keep left if nums[lo] <= target < nums[mid], else right
    else:                                                 # right half sorted
        keep right if nums[mid] < target <= nums[hi], else left
return false