这道题比较简单，就是二分查找。思路就是每次取中间，如果等于目标即返回，否则根据大小关系切去一半。因此算法复杂度是O(logn)，空间复杂度O(1)。代码如下：
public int searchInsert(int[] A, int target) {
if(A == null || A.length == 0)
{
return 0;
}
int l = 0;
int r = A.length-1;
while(l<=r)
{
int mid = (l+r)/2;
if(A[mid]==target)
return mid;
if(A[mid]<target)
l = mid+1;
else
r = mid-1;
}
return l;
}注意以上实现方式有一个好处，就是当循环结束时，如果没有找到目标元素，那么l一定停在恰好比目标大的index上，r一定停在恰好比目标小的index上，所以个人比较推荐这种实现方式。Search Insert Position -- LeetCode,布布扣,bubuko.com
Search Insert Position -- LeetCode
原文：http://blog.csdn.net/linhuanmars/article/details/20278967