Simple Java solution using binary search


  • 0
    Y
    public int searchInsert(int[] nums, int target) {
            return binarySearch(nums, target, 0, nums.length - 1);
        }
        
        private int binarySearch(int[] nums, int target, int start, int end) {
            if (start == end){
                return target <= nums[start] ? start : start + 1;
            }
            if (start < end) {
                int midpoint = (start + end) / 2;
                if (target < nums[midpoint]) {
                    return binarySearch(nums, target, start, midpoint);
                }
                if (target > nums[midpoint]) {
                    return binarySearch(nums, target, midpoint + 1, end);
                }
                if (target == nums[midpoint]) {
                    return midpoint;
                }
            }
            return 0;
        }
    

  • 0

    Why not just set end = mid and start = mid + 1 instead of binarySearch(nums, target, start, midpoint); and binarySearch(nums, target, midpoint + 1, end);
    Saves the recursive calls right?


  • 0
    Y

    Yes, you are right. It do save one recursive call. But anyway, there is at most one of them being called. So I think either way would be ok.


Log in to reply
 

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