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


  • 0
    S
    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;
        }
    };
    

Log in to reply
 

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