Rotated Array Search II

Find a target in a rotated sorted array that may contain duplicates.

binary-search array search duplicates

You are given a rotated sorted array `nums` that may contain duplicate values. The array was originally sorted in ascending order, then rotated at an unknown pivot. For example, `[0,1,2,4,4,5,6,7]` might become `[4,5,6,7,0,1,2,4]`. Write a function `search_rotated(nums, target)` that returns `True` if `target` is present in `nums`, and `False` otherwise. Your solution must run in O(log n) average time complexity, even in the presence of duplicates (worst-case O(n) when many duplicates cause ambiguity).

Constraints

0 <= nums.length <= 10^5
-10^9 <= nums[i], target <= 10^9
Array is a rotation of a sorted (non-decreasing) array, with possible duplicates.

Example

>>> search_rotated([4,5,6,7,0,1,2], 0)
True
>>> search_rotated([4,5,6,7,0,1,2], 3)
False
>>> search_rotated([1,1,1,3,1], 3)
True
>>> search_rotated([1], 1)
True

20 points ~20 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Use binary search but handle the case where `nums[mid] == nums[left] == nums[right]` by shrinking the search range.

When `nums[left] <= nums[mid]`, the left half is sorted; check if target lies in that half to decide which side to keep.

If `nums[mid] <= nums[right]`, the right half is sorted; similarly check target's presence there.

Remember to handle equal elements at the ends to avoid incorrect sorted-half decisions.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.