SearchInsertPosition35.java

/**
 * Given a sorted array and a target value, return the index if the target is
 * found. If not, return the index where it would be if it were inserted in
 * order.
 *
 * You may assume no duplicates in the array.
 *
 * Here are few examples.
 * [1,3,5,6], 5 → 2
 * [1,3,5,6], 2 → 1
 * [1,3,5,6], 7 → 4
 * [1,3,5,6], 0 → 0
 */


public class SearchInsertPosition35 {
    public int searchInsert(int[] nums, int target) {
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] >= target) {
                return i;
            }
        }
        return nums.length;
    }


    /**
     * https://discuss.leetcode.com/topic/7874/my-8-line-java-solution
     */
    public int searchInsert2(int[] A, int target) {
        int low = 0, high = A.length-1;
        while(low <= high){
            int mid = (low + high) / 2;
            if(A[mid] == target) return mid;
            else if(A[mid] > target) high = mid-1;
            else low = mid+1;
        }
        return low;
    }


    public int searchInsert3(int[] nums, int target) {
        if (nums.length == 0) return 0;
        if (target > nums[nums.length-1]) return nums.length;
        int l = 0;
        int r = nums.length-1;
        
        while (l < r) {
            int mid = (r - l) / 2 + l;
            if (nums[mid] == target) return mid;
            else if (nums[mid] < target) {
                l = mid + 1;
            } else {
                r = mid;
            }
        }
        return l;
    }

}