public class SearchInsertPosition {
	// find the 1st position >= target
    public static int searchInsert(int[] nums, int target) {
        int start = 0, end = nums.length-1;
        while(start + 1 < end) {
            int mid = start + (end - start) / 2;
            if(nums[mid] == target)
                return mid;
            else if(nums[mid] > target)
                end = mid;
            else
                start = mid;
        }
        
        if(nums[start] >= target)
            return start;
        if(nums[end] >= target)
            return end;
        return end + 1;
        
    }

    public static void main(String[] args) {
    	int[] nums = {1,3,5,6};
    	System.out.println(searchInsert(nums, 5));
    	System.out.println(searchInsert(nums, 2));
    	System.out.println(searchInsert(nums, 7));
    	System.out.println(searchInsert(nums, 0));
    	System.out.println(searchInsert(new int[]{1}, 1));
    }
}
@@ -1,12 +1,368 @@
+/**%0A *  Given a sorted array and a target value, return the index if the target is found. %0A *  If not, return the index where it would be if it were inserted in order.%0A *%0A *  You may assume no duplicates in the array.%0A *  Here are few examples. %0A *  %5B1,3,5,6%5D, 5 %E2%86%92 2%0A *  %5B1,3,5,6%5D, 2 %E2%86%92 1%0A *  %5B1,3,5,6%5D, 7 %E2%86%92 4%0A *  %5B1,3,5,6%5D, 0 %E2%86%92 0%0A *%0A *  Author: matao%0A */%0A%0A
 public class

add comment