← DSA Atlas
Dedicated problem page · #81

Search in Rotated Sorted Array II

MediumBinary SearchBinary search on a rotated array with duplicatesBinary search
Solve on LeetCode ↗
81
MediumBinary SearchBinary searchBinary search on a rotated array with duplicates

Search in Rotated Sorted Array II

An ascending sorted array that may contain duplicates has been rotated at an unknown pivot. Given the rotated array nums and a target, return true if target is present, otherwise false.

Open official problem prompt ↗
In plain English

Decide membership in a sorted-then-rotated array where duplicate values can obscure the pivot.

Picture it like this

A deck sorted then cut at a random spot. Usually you can see which side of the cut is still in order; but when the top, middle, and bottom cards all read the same, you can only peel one card off each end and look again.

Example
Input
nums = [2,5,6,0,0,1,2], target = 0
Output
true
Why
0 appears at indices 3 and 4, so the target exists in the array.
Constraints
1 <= nums.length <= 5000-10^4 <= nums[i] <= 10^4nums is guaranteed to be an ascending array rotated at some pivot-10^4 <= target <= 10^4
Pattern lesson

See the pattern, then code

Binary search on a rotated array with duplicates
Recognition clue

A rotated sorted array plus the phrase 'may contain duplicates' is the tell — it is problem 33 but with equal endpoints that hide which half is sorted.

↗
Binary Search

Sorted data or a monotonic true/false condition over a possible answer.. At each step one half is still sorted; you can tell which by comparing nums[lo] to nums[mid]. The one trap is nums[lo]==nums[mid]==nums[hi], where you cannot decide, so you shrink both ends by one.

New words, made simpleKnow these before the algorithm
Pivot
The rotation point where the array wraps from its largest back to its smallest value
Sorted half
The side of mid that is still in strictly non-decreasing order
Degenerate case
nums[lo]==nums[mid]==nums[hi], where neither half is provably sorted
Approaches from first idea to best ideaCompare the trade-offs
ApproachHow it thinksCost
Linear scan

Always works but throws away the sorted structure.

Check every element for equality with target.

Time O(n)Space O(1)
Best choiceBinary search with duplicate handling

As fast as possible; only pathological all-equal input degrades it.

Detect the sorted half each step; when all three endpoints tie, shrink both ends by one.

Time O(log n) average, O(n) worstSpace O(1)
The rule we keep true

Invariant

target, if present, always remains within the window [lo, hi].

Why this is correct

Reasoning

Whenever endpoints are not all equal, comparing nums[lo] to nums[mid] identifies a genuinely sorted half, and a simple range test says whether target belongs there, so exactly one half is discarded safely. The lo++/hi-- fallback removes only elements equal to nums[mid], which cannot be the target unless already caught, so it never skips a valid answer.

The algorithm in three movesSay these aloud before coding
1If nums[mid] equals target, return true

lo=0 hi=6 mid=3 -> nums[3]=0 == target, return true

2If the three endpoints are equal, drop lo++ and hi-- to break the tie

3Otherwise identify the sorted half and check if target lies inside it

4Recurse into the half that could contain target

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example
20
51
62
03
04
15
26
1 · Readlo=0, hi=6
2 · AskIs nums[mid] the target?
3 · Update statemid=3, nums[3]=0
4 · Result0 == target, return true immediately
Key takeaway

The midpoint lands directly on a 0, so the search succeeds immediately.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

  1. 1
    Lines 6-7Direct hit check

    Return as soon as the midpoint equals target.

  2. 2
    Lines 8-10Break the ambiguous tie

    When endpoints are all equal, shrink both ends since neither half is decidable.

  3. 3
    Lines 11-15Left half is sorted

    If target lies in [nums[lo], nums[mid]) search left, else right.

  4. 4
    Lines 16-20Right half is sorted

    If target lies in (nums[mid], nums[hi]] search right, else left.

Make it stick

Edge cases, mistakes, and one self-check

E

Edge cases to test

  • All elements identical (worst case O(n))
  • Array not actually rotated (rotation of 0)
  • Target absent but equal to a boundary value
  • Single-element array
!

Common beginner mistakes

  • Using strict < instead of <= when testing nums[lo] <= nums[mid], which mishandles the two-element window
  • Forgetting the all-equal branch and looping forever or wrongly discarding a half
  • Assuming worst case stays logarithmic despite duplicates
Check your understanding

Why can this problem be O(n) in the worst case while problem 33 (no duplicates) stays O(log n)?

More in Binary Search

#33Search in Rotated Sorted ArrayBinary search on a rotated array#153Find Minimum in Rotated Sorted ArrayBinary search for the rotation point#875Koko Eating BananasBinary search on the answer#4Median of Two Sorted ArraysBinary search on the partition#34Find First and Last Position of ElementLower-bound binary search on both ends#35Search Insert PositionLower-bound binary search