Straight forward binary search


  • 0
    O
    int search(vector<int>& nums, int target) 
    {
        if(nums.size()==0)
            return -1;
        int l=0, r = nums.size()-1, m=0;
        while(l<=r)
        {
            m = l + (r-l)/2;
            if(nums[m] == target)
                return m;
            else
            {
                // if right side is sorted
                if(nums[m] < nums[r])  
                {
                    // is it in the right side?
                    if(nums[m]<target && target <= nums[r])
                        l = m+1;
                    else
                        r = m-1;
                }
                // left sided is sorted
                else
                {
                    // is target in left side?
                    if(nums[l]<=target && target < nums[m])
                        r = m-1;
                    else
                        l = l+1;
                }
            }
        }
        return -1;
    }

Log in to reply
 

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