Description
There is an integer array nums sorted in non-decreasing order (not necessarily with distinct values). Given the array after rotation and an integer target, return true if target is in nums, or false otherwise.
Examples
Input:
nums = [2,5,6,0,0,1,2], target = 0Output:
trueExplanation:
0 is found in the array.
Input:
nums = [2,5,6,0,0,1,2], target = 3Output:
falseExplanation:
The target value does not exist in the given data structure.
Input:
nums = [1,1,1,3,1], target = 3Output:
trueExplanation:
The array was originally [1,1,1,1,3] and rotated. Despite having many duplicate values that make it challenging to determine which part is sorted, it is possible to still find the target 3 at index 3.
Constraints
- •
1 ≤ nums.length ≤ 5000 - •
-10⁴ ≤ nums[i] ≤ 10⁴