Find min Binary Search Style


  • 0
    O

    like binary search, we check start and mid, and we always search for the unsorted half instead of the sorted half

    int findMin(vector<int>& nums) 
    {
        if(nums.size()==0)
            return INT_MIN;
        
        
        int l=0, r=nums.size()-1, m=0;
        
        while(l<=r)
        {
            if(nums[l]<=nums[r])
                return nums[l];
    
            int m=l+(r-l)/2;
            
            // no need to check m>0 cuz nums[l] <= nums[r] does the job
            if(nums[m] < nums[m-1])
                return nums[m];
            
            if(nums[m] <= nums[r])
                r = m-1;
            else
                l = m+1;
        }
        return nums[l];
    }

Log in to reply
 

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