题目

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

原题链接（点我）

解题思路

给一个排序数组和一个数，寻找该数在数组的位置或者插入位置。本题考查对二分查找的理解和二分查找树。二分查找查找失败的位置就是该数在数组中该插入的位置。

代码实现

class Solution {
public:
    int searchInsert(int A[], int n, int target) {
        if(A==NULL || n<=0) return -1;
        int begin=0, end=n-1;
        while(begin<=end){
            int mid = (begin+end)/2;
            if(A[mid] == target) return mid;
            if(A[mid] > target) 
                end = mid-1;
            else
                begin = mid+1;
        }
        return begin;
    }
};