Share my 6ms c++ solution (faster than 99%)


  • 0
    I

    it is a typical binary search method. There is no significant difference from other binary search methods.
    the key is realizing the fact that if you narrow down the range to a single element, you can know the correct answer immediately. correct position = nums[i]>=target? i : i+1;

    int searchInsert(vector<int>& nums, int target) {
        return binarySearchInsert(nums, target, 0, nums.size()-1);
    }
    int binarySearchInsert(vector<int>& nums, int target, int left, int right)
    {
        // when there is only one number
        if(left >= right)
        {
            if(nums[left] >= target)
            {
                return left;
            }
            else 
            {
                return left+1;
            }
        }
        // when there are more than one num
        int mid = left + (right-left)/2;
        if(nums[mid] == target)
        {
            return mid;
        }
        else if (nums[mid] <= target)
        {
            return binarySearchInsert(nums, target, mid+1, right);
        }
        else
        {
            return binarySearchInsert(nums,target,left, mid);
        }
    }

Log in to reply
 

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