Search Insertion 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.

分析：

这道题是标准的二分法已经毫无疑问，只需要注意的是，最后判断插在什么位置的时候要仔细研究例子,分类讨论。

解法：

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

        if (target > A[end]) {
            return end + 1;
        } else if (target > A[start]) {
            return start + 1;
        } else {
            return start;
        }
    }
};