# My concise C++ solution with explanation (o(N) worst case, o(logN) on average)

• The idea is the same as the previous one without duplicates

``````1) everytime check if targe == nums[mid], if so, we find it.
2) otherwise, we check if the first half is in order (i.e. nums[left]<=nums[mid])
and if so, go to step 3), otherwise, the second half is in order,   go to step 4)
3) check if target in the range of [left, mid-1] (i.e. nums[left]<=target < nums[mid]), if so, do search in the first half, i.e. right = mid-1; otherwise, search in the second half left = mid+1;
4)  check if target in the range of [mid+1, right] (i.e. nums[mid]<target <= nums[right]), if so, do search in the second half, i.e. left = mid+1; otherwise search in the first half right = mid-1;
``````

The only difference is that due to the existence of duplicates, we can have nums[left] == nums[mid] and in that case, the first half could be out of order (i.e. NOT in the ascending order, e.g. [3 1 2 3 3 3 3]) and we have to deal this case separately. In that case, it is guaranteed that nums[right] also equals to nums[mid], so what we can do is to check if nums[mid]== nums[left] == nums[right] before the original logic, and if so, we can move left and right both towards the middle by 1. and repeat.

``````class Solution {
public:
bool search(vector<int>& nums, int target) {
int left = 0, right =  nums.size()-1, mid;

while(left<=right)
{
mid = (left + right) >> 1;
if(nums[mid] == target) return true;

// the only difference from the first one, trickly case, just updat left and right
if( (nums[left] == nums[mid]) && (nums[right] == nums[mid]) ) {++left; --right;}
else if(nums[left] <= nums[mid])
{// first half is in order
if( (nums[left]<=target) && (nums[mid] > target) ) right = mid-1; // if target is in the first half
else left = mid + 1;
}
else
{ // second half is in order
if((nums[mid] < target) &&  (nums[right] >= target) ) left = mid+1; // if target is in the second half
else right = mid-1;
}
}
return false;
}
};``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.