problem：
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
thinking：
（1）又是对二分搜索的变形，策略很简单，不光要判断 A[mid] 是否等于arget，还要判断target是否落在区间（mid-1，mid+1）内，即：
if(A[mid]==target || (A[mid-1]<target&&target<A[mid+1]) )
{
if(A[mid]==target || target<A[mid])
return mid;
else
return mid+1;
}（2）注意边界条件比较多class Solution {
public:
int searchInsert(int A[], int n, int target) {
if(n==0)//空数组
return 0;
if(n==1)//一个元素
{
if(A[0]>=target)
return 0;
else
return 1;
}//if
if(A[0]>=target)//target落在数组最前方
return 0;
if(A[n-1]<target)//target落在最后面
return n;
int res=binary_search(A,0,n-1,target);
return res;
}
protected:
int binary_search(int A[], int left, int right, int target)
{
if(left>right)
return -1;
int mid = (left+right)/2;
if(A[mid]==target || (A[mid-1]<target&&target<A[mid+1]) )
{
if(A[mid]==target || target<A[mid])
return mid;
else
return mid+1;
}
else if(A[mid]>target)
return binary_search(A,left,mid-1,target);
else
return binary_search(A,mid+1,right,target);
}
};
leetcode 题解 || Search Insert Position 问题
原文：http://blog.csdn.net/hustyangju/article/details/44618471