Search Insert Position

Search Insert Position

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

Challenge

(log(n)) time

思路：

标准的二分查找。题目中说没有重复的数。如果直接查到这个数，直接返回此数位置即可。如果没有查到就退出循环（注意并不一定是没有此数），找第一个大于等于此数的数字的位置即可。

public class Solution {
    /** 
     * param A : an integer sorted array
     * param target :  an integer to be inserted
     * return : an integer
     */
    public int searchInsert(int[] A, int target) {
        // write your code here
        if (A == null || A.length == 0) {
            return 0;
        }
        
        int start = 0, end = A.length - 1;
        
        while (start + 1 < end) {
            int mid = start + (end - start) /  2;
            if (A[mid] == target) {
                return mid;
            }
            if (A[mid] < target) {
                start = mid;
            }
            if (A[mid] > target) {
                end = mid;
            }
        }
        
        if (A[start] >= target) {
            return start;
        }
        else if (A[end] >= target) {
            return end;
        }
        else {
            return end + 1;
        }
    }
}