Java modified Binary Search solution


  • 0
    G

    The idea is to use a normal binary search and if we find the target number return index of target, otherwise if current binary search window (Right - Left) == 1 or 0 (diff between high and low is 0 or 1) then it means element must fit inside this interval, target index would be either h +1, h or mid (mid will be equal to l in this case). algorithm below:

    public class Solution {
        public int searchInsert(int[] nums, int target) {
        	if (target < nums[0]) {
        		return 0;
        	} 
        	if (target > nums[nums.length-1]) {
        		return nums.length;
        	}     	
            
            return binSearch(nums, 0, nums.length - 1, target);
        }
        
        private int binSearch(int[] nums, int l, int h, int t) {
            if (l > h) {
                return - 1;
            }
            int m = (l + h) / 2;
            
            if (t == nums[m]) {
                return m;
            } 
            if ((h-l) == 1 || (h-l) == 0) {
            	if (t > nums[h]) {
            		return h+1;
            	} else if (t > nums[m]) {
            		return h;
            	} else {
            		return m;
            	}
            }
            
            else if (nums[m] > t) {
                return binSearch(nums, l, m - 1, t);
            }
            return binSearch(nums, m + 1, h, t);
        }
    }
    

Log in to reply
 

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