mediumBinary SearchPure DSA~25 min
Search a Rotated Sorted Array with Duplicates
A circular buffer of sorted config snapshots may contain duplicate versions and has been rotated at an unknown pivot. Decide whether a target version exists in it.
Problem
Given an integer array nums that was originally sorted ascending (possibly with duplicates) then rotated at an unknown pivot, and a target value, return true if target is present, else false. Aim for better than linear time on average.
Input
An integer array nums (rotated, may contain duplicates) and an integer target.
Output
A boolean: whether target exists in nums.
Constraints
- 1 <= nums.length <= 5000
- -10^4 <= nums[i], target <= 10^4
- nums is a rotation of a non-decreasing array.
Examples
Example 1
Input
nums = [2,5,6,0,0,1,2], target = 0
Output
true
0 appears in the array.
Example 2
Input
nums = [2,5,6,0,0,1,2], target = 3
Output
false
3 is not present.