Search in Rotated Sorted Array II
Medium · binary search
A list of integers was sorted in ascending order, then rotated: some number of values from the front were moved, in order, to the back. For example [0, 1, 2, 2, 4, 5] rotated by 4 becomes [4, 5, 0, 1, 2, 2]. Rotating by 0 leaves the list as it was.
The list nums is the result. It can contain duplicate values, and you are not told how far it was rotated.
Return true if target appears in nums, and false otherwise.
Examples
Example 1
Input: nums = [4, 5, 0, 1, 2, 2], target = 0
Output: true
Example 2
Input: nums = [4, 5, 0, 1, 2, 2], target = 3
Output: false
Example 3
Input: nums = [1, 1, 1, 0, 1], target = 0
Output: true
The list is [0, 1, 1, 1, 1] rotated by 2.
Constraints
- 1 <= len(nums) <= 5000
- -10^4 <= nums[i] <= 10^4
- -10^4 <= target <= 10^4
- nums is a sorted list that has been rotated some number of times.