Problem

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.

Example
[1,3,5,6], 5 → 2

[1,3,5,6], 2 → 1

[1,3,5,6], 7 → 4

[1,3,5,6], 0 → 0

思路

• find the index of first element <= target
• at the end, we should examine the possible position of start, end , and target
• 需要通过以上的example得出插入的位置是第一个大于等于target的位置
• 列出只有两个元素时候的各种可能性

    public int searchInsert(int[] A, int target) {
        if (A == null || A.length == 0) {
            return 0;
        }

        int start = 0;
        int end = A.length - 1;

        while (start + 1 < end) {
            int mid = start + (end - start) / 2;
            if (A[mid] < target) {
                start = mid;
            } else if (A[mid] > target) {
                end = mid;
            } else {
                end = mid;
            }
        }
        // end target
        if (A[end] < target) return end + 1;

        // target start
        if (A[start] >= target) return start;

        // start target end
        return end;
    }