C++ 3ms solution, binary search according to 4 situations


  • 0
    K
    class Solution {
    public:
        int bs(const vector<int> &nums,int target,int left,int right) {
            if(left>=right)
            {
                if(nums[right]!=target) return -1;
                return right;
            }
            int mid=(left+right)/2;
            if(target==nums[mid])return mid;
    
            // right side is ordered and target is on the right side
            if(nums[mid]<target && target<=nums[right]) return bs(nums,target,mid+1,right);
    
            // left side is ordered and target is on the left side
            if(nums[left]<=target && target<nums[mid]) return bs(nums,target,left,mid);\
    
            // right side is ordered and target is NOT on the right side
            if(nums[mid]<nums[right]) return bs(nums,target,left,mid);
    
            // left side is ordered and target is NOT on the left side
            return bs(nums,target,mid+1,right);
        }
        int search(vector<int>& nums, int target) {
            if(nums.size()<1)return -1;
            return bs(nums,target,0,nums.size()-1);
        }
    };
    

Log in to reply
 

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