Determine whether a target value exists in a rotated sorted array that may contain duplicates.
You are given an integer array that was originally sorted in non-decreasing order, then rotated at an unknown pivot. The array may contain duplicate values.
Write a function to determine whether a given target value exists in the array.
Because duplicates are allowed, the usual binary search logic may become ambiguous in some cases. Your solution should still be efficient on average and handle all valid inputs correctly.
Input Format
- An integer array
numsin non-decreasing order, rotated at an unknown pivot - An integer
target
The array may contain duplicates.
Output Format
- Return
trueiftargetexists innums - Otherwise return
false
Constraints
1 <= nums.length- Values may be duplicated
- The array is a rotation of a sorted non-decreasing array
- Return a boolean result
Example 1
Input
nums = [2,5,6,0,0,1,2], target = 0
Output
true
Explanation
The value 0 appears in the array.
Example 2
Input
nums = [2,5,6,0,0,1,2], target = 3
Output
false
Explanation
The value 3 does not appear in the array.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.