Loading problem…
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`) such that the resulting array is `[nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]` (**0-indexed**). 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`. You must decrease the overall operation steps as much as possible.
Example 1
Input: nums = [2,5,6,0,0,1,2], target = 0
Output: true
Explanation: The sorted array [0,0,1,2,2,5,6] was rotated to start at 2. The target 0 appears at indices 3 and 4, so the answer is true.
Example 2
Input: nums = [2,5,6,0,0,1,2], target = 3
Output: false
Explanation: 3 does not appear anywhere in the array.
Example 3
Input: nums = [1,0,1,1,1], target = 0
Output: true
Explanation: The array is [0,1,1,1,1] rotated by one position, and 0 sits at index 1. Because both ends are 1, you can't tell which half is sorted, but the value is still there, so the answer is true.
Rotated binary search normally checks which half is sorted by comparing nums[mid] to nums[left]. Duplicates break that test when nums[left] == nums[mid] == nums[right] — you can't tell which side is sorted, so shrink both ends by one and retry.
Run checks all cases above. Submit evaluates all test cases.