The sorted array is rotated once, and we might have duplicate (i.e., [0,0,1,2,2,5,6] might become [2,5,6,0,0,1,2]).
We will still use binary search but this time the duplicate will give us an edge case:
[1,1,1,1,1,1,1,1,1,2,3,4] rotate -> [1,2,3,4,1,1,1,1,1,1,1]
low = 1, high = 1 and mid = 1 and we don’t know which part is sorted so we can either low ++ or high — to edge toward an interval where at least we know [low,mid] or [mid, high] is sorted.
class Solution {
public:
bool search(vector<int>& nums, int target) {
int low = 0;
int high = nums.size() - 1;
while(low <= high){
int mid = low + (high - low) / 2;
if(nums[mid] == target)
return true;
if(nums[low] < nums[mid]){//low-mid are sorted
if(nums[low] <= target && target < nums[mid]){
high = mid - 1;
}
else{
low = mid + 1;
}
}
else if(nums[mid] < nums[low]){ //mid-high are sorted
if(nums[mid] < target && target <= nums[high]){
low = mid + 1;
}
else{
high = mid - 1;
}
}
else{
low ++;
}
}
return false;
}
};
bugs
else if condition
In else if, I first used
else if(nums[mid] < nums[high]
to decide if [mid, high] is sorted but it will fail at test case such as [3,1,1] t = 3.
low = 0 high = 2 mid = 1
we see that nums[low] !< nums[mid] so [low, mid] is not sorted so [mid, high] should be sorted, but our elseif statement is not true because nums[mid] == nums[high]. So we should just change elseif to the compliement of
if(nums[low] < nums[mid])
Which is
else if(nums[low] > nums[mid]
(Not exact complement since equality is already tested)