You are given an integer array nums sorted in ascending order (not necessarily distinct values), and an integer target.
Suppose that nums is rotated at some pivot unknown to you beforehand (i.e., [0,1,2,4,4,4,5,6,6,7] might become [4,5,6,6,7,0,1,2,4,4]).
If target is found in the array return its index, otherwise, return -1.
Input: nums = [2,5,6,0,0,1,2], target = 0
Output: true
Input: nums = [2,5,6,0,0,1,2], target = 3
Output: false
1 <= nums.length <= 5000
-104 <= nums[i] <= 104
nums is guaranteed to be rotated at some pivot.
-104 <= target <= 104
Solutions (Click to expand)
This problem is a variation of Search in Rotated Sorted Array where the input array allows for repeated numbers. This brings up a new edge case we have to account for.
If we being up the idea of two sorted sub arrays we run into an issue with the following input
target = 2
[1,1,1,1,1,1,2,1]
We are unable to partition the array correctly with binary search because the beginning end and middle numbers are all the same. In Search in Rotated Sorted Array the array is partitioned with binary search based on where we believe arrays pivot or smallest number starts. We're unable to make such comparison when all beginning middle and end numbers are the same.
To fix this, we added a loop at the very beginning that compares the beginning and end numbers and increments our left boundary until we find a new number.