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

 

思路：

与普通二分搜索的唯一区别在于 可能插入的位置是没找到时 l 的值

int searchInsert(int A[], int n, int target) {    int l = 0, r = n - 1;    while(l <= r)    {        int m = (l + r) / 2;        if(A[m] == target)            return m;        else if(A[m] > target)            r = m - 1;        else            l = m + 1;    }    return l;       //注意 就这里不一样  最后r = l - 1 返回l就可以了 就是应该插入的位置}