# LC 81, search in rotated array 2

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)