Easy binary search solution Java


  • 0
    public class Solution {
        
        private int helper(int[] nums, int start, int end, int target) {
            if(start==end) {
                if(nums[start]==target)
                    return start;
                else if(target > nums[start])
                    return -(start+1)-1; // decrease by additional 1 to differentiate with 0
                else
                    return -start-1; // decrease by additional 1 to differentiate with 0
            }
            int mid = (start+end)/2;
            if(nums[mid] == target)
                return mid;
            else if(target > nums[mid])
                return helper(nums, mid+1, end, target); // note mid must not be the insertion point,so start with mid+1
            else
                return helper(nums, start, mid, target); // note both start and mid must be inclusive cause mid can be the insertion point
        }
        
        public int searchInsert(int[] nums, int target) {
            int res = helper(nums, 0, nums.length-1, target);
            return res>=0 ? res : -(res+1);
        }
    }

Log in to reply
 

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