pic

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.

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

分析

题目的意思是，给定一个排序的整形数组和一个数值，如果这个数值能在数组中找到，就返回这个数值在数组的下标；如果找不到，那么就返回应该按序插入的位置下标。

     * 既然题目说了是排序的数组，很显然要用二分查找
     * 二分查找有两点需要注意：死循环和漏元素
     * 还要注意当所有数组元素都小于@target的特殊情况

Code

class Solution {
public:
    /* 
     * 既然题目说了是排序的数组，很显然要用二分查找
     * 二分查找有两点需要注意：死循环和漏元素
     * 还要注意当所有数组元素都小于@target的特殊情况
     * */
    int searchInsert(int A[], int n, int target) {
        // IMPORTANT: Please reset any member data you declared, as
        // the same Solution instance will be reused for each test case.
        int left = 0, right = n-1, middle = 0;
        if( !A || n < 1)
            return 0;
        while( left < right )
        {
            middle = left + ((right - left) >> 1);
            if(A[middle] == target)
                return middle;
            else if( A[middle] < target )
            {
                left = middle + 1;
            }
            else
                //这里不能用right = middle+1
                right = middle; 
        }
        // 当@target大于所有数组元素
        if(A[right] < target)
            return right + 1;
        // 当插入位置是第一个大于@target的位置
        if(left == right)
            return left;
    }
};

pic