There is an integer array `nums` sorted in non-decreasing order (not necessarily with distinct values).
Before being passed to your function, `nums` is **rotated** at an unknown pivot index `k` (`0 <= k < nums.length`).
Given the array `nums` after the rotation and an integer `target`, return `true` if `target` is in `nums`, or `false` if it is not in `nums`.
### Constraints
- `1 <= nums.length <= 5000`
- `-10^4 <= nums[i], target <= 10^4`
- `nums` is guaranteed to be rotated at some pivot.
### Input Format
First line contains the target integer.
Second line contains space-separated integers representing `nums`.
### Output Format
Print `true` if target is present, otherwise `false`.
Sample Cases
Example 1Sample Case
Input: 0
2 5 6 0 0 1 2
Output: true
Example 2Sample Case
Input: 3
2 5 6 0 0 1 2
Output: false
Example 3Sample Case
Input: 0
2
Output: false
Example 4Sample Case
Input: 0
0
Output: true
Constraints
Runtime Limit: 2000 ms per test batch
Memory Limit: 256 MB
Standard I/O stream reading
Official submissions are evaluated against hidden test cases on the server to verify time & memory complexity.