← Back to DSA Animator
Search in Rotated Sorted Array II LC #81 Medium Binary Search · Duplicates
Problem

There is an integer array nums sorted in non-decreasing order (possibly with duplicates), which is possibly rotated at an unknown pivot index k. Given nums and an integer target, return true if target is in nums, or false if it is not. The key difference from LC #33: duplicates are allowed, making the "SKIP DUPS" case necessary when nums[lo]==nums[mid]==nums[hi].

Example 1
Input:nums = [2,5,6,0,0,1,2], target = 0
Output:true
Explanation:0 is in the array.
Example 2
Input:nums = [2,5,6,0,0,1,2], target = 3
Output:false
Explanation:3 is not in the array.
Example 3
Input:nums = [1,0,1,1,1], target = 0
Output:true
Explanation:0 is in the array — found after skipping duplicates.
Constraints: 1 ≤ nums.length ≤ 5000  |  −10⁴ ≤ nums[i], target ≤ 10⁴  |  nums is sorted and possibly rotated, duplicates allowed.
Try Examples
Custom:
Array — Rotated with Duplicates
Left half sorted
Right half sorted
mid pointer
SKIP DUPS (lo++, hi--)
Target found
State Variables
lo
—
mid
—
hi
—
nums[lo]
—
nums[mid]
—
nums[hi]
—
Situation
—
Step Logic
Press ▶ Play or Next Step to begin the animation.
Ready
0 / 0
Select an example above and press Play.
Algorithm
1
Init lo=0, hi=n-1. Loop while lo <= hi, compute mid.
2
If nums[mid]==target: return true.
3
SKIP DUPS: if nums[lo]==nums[mid]==nums[hi] → ambiguous, do lo++; hi--.
4
Else if nums[lo]<=nums[mid]: left half sorted → search or discard left.
5
Else: right half sorted → search or discard right.
6
Loop exhausted without match → return false.
Time
O(n) worst
Space
O(1)
Why SKIP DUPS is Necessary

In LC #33 (no duplicates), nums[lo] <= nums[mid] reliably means the left half is sorted. But with duplicates, nums[lo]==nums[mid]==nums[hi] is possible — we literally cannot tell which side the rotation pivot is on, so neither half can be confidently declared sorted.

The fix is simple but powerful: increment lo and decrement hi to skip one known duplicate on each end. This degrades worst-case to O(n) (e.g., [1,1,1,1,1]) but preserves O(log n) average behaviour on random inputs.