# My C++ sloution:easy to read,easy to understand,O(logn) on average ,O(n) in worst.

• ``````class Solution {
public:
bool search(vector<int>& nums, int target) {
const int n=nums.size();
if(n==0) return false;
int left=0;
int right=n-1;
while(left<=right){
int mid=left+(right-left)/2;
if(nums[mid]==target) return true;
//this worst sitution so use line search
if(nums[mid]==nums[left]&&nums[mid]==nums[right]){
return search2(nums,left,right,target);
}//left part use line search
else if(nums[mid]==nums[left]){
if(search2(nums,left,mid,target)){
return true;
}
left=mid+1;
}//right part use line search
else if(nums[mid]==nums[right]){
if(search2(nums,mid,right,target)){
return true;
}
right=mid-1;
}//no duplicate  mid element in left part
else if(nums[mid]>nums[right]){
if(target<nums[mid]&&target>=nums[left]){
right=mid-1;
}
else{
left=mid+1;
}
}//no duplicate mid element in right part
else if(nums[mid]<nums[left]){
if(target>nums[mid]&&target<=nums[right]){
left=mid+1;
}
else{
right=mid-1;
}
}//no duplicate no rotate situtation
else{
if(nums[mid]<target){
left=mid+1;
}
else{
right=mid-1;
}
}
}
return false;
}
//line search method
bool search2(vector<int> &nums,int start,int end,int target){
for(int i=start;i<end;++i){
if(nums[i]==target) return true;
}
return false;
}
};
``````

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