# My 8ms C++ solution (o(logn) on average, o(n) worst case)

• 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])
{
if( (nums[left]<=target) && (nums[mid] > target) ) right = mid-1;
else left = mid + 1;
}
else
{
if((nums[mid] < target) &&  (nums[right] >= target) ) left = mid+1;
else right = mid-1;
}
}
return false;
}
};``````

• I think this is the most intuitive answer!

• My answer is similar to yours. But we don't have to check duplicated items in every loop, instead we check once.

``````class Solution {
public:
bool search(vector<int>& nums, int target) {
if(nums.size() == 0) return false;
// Find the non-duplicated head: h
int h = 0;
while(h != nums.size()-1 && nums[h] == nums[nums.size()-1]) h++;
// Previous algorithm can deal with duplicated items if the head of array is not a duplicated item
int L = h, R = nums.size()-1, M = (L+R)/2;
while(L < R){
if(nums[M] == target)
return true;
else if((nums[h] <= target) ^ (target <= nums[M]) ^ (nums[M] < nums[h]) == false)
R = M;
else
L = M+1;
M = (L+R)/2;
}
return (L == R && nums[L] == target)? true : false;
}
};
``````

• This post is deleted!

• @dong.wang.1694
Thanks. With your inspiration. I think I come up a crystal clear solution for this problem. Also works for no duplicates version.

``````class Solution {
public:
bool search(vector<int>& A, int t) {
if (A.empty())
return false;

int l = 0, r = A.size() - 1;

while (l < r) {
int m = l + (r - l) / 2;
if (A[m] == t) return true;
if (A[l] < A[m]) {
if (A[l] <= t && t < A[m]) {
r = m - 1;
} else {
l = m + 1;
}
} else if (A[m] < A[r]) {
if (A[m] < t && t <= A[r]) {
l = m + 1;
} else {
r = m - 1;
}
} else {
if (A[l] == A[m]) l++;
if (A[m] == A[r]) r--;
}
}

return A[l] == t? true : false;
}
};
``````

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