A clean Java solution using Binary Search


  • 0
    W

    This problem is similar to binary search. The gist of the problem is, while doing binary search, if "begin" position becomes greater than "end" position, the insertion point is the begin position.

    Also note that whenever, begin > end, the difference between them is always 1 i.e. begin - end = 1.

    public class Solution {
        public int searchInsert(int[] nums, int target) {
            return binarySearch(nums, 0, nums.length - 1, target);
        }
        
        int binarySearch(int[] nums, int begin, int end, int target) {
            if(begin > end)
                return begin;
            int mid = (begin + end) / 2;
            if(nums[mid] == target)
                return mid;
            if(target < nums[mid])
                return binarySearch(nums, begin, mid - 1, target);
            return binarySearch(nums, mid + 1, end, target);
        }
    }

Log in to reply
 

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