这题直接用遍历的话时间复杂度也只有O(n)，但是没必要，因为通过将二分查找法进行一定的修改就可以做到，二分查找法比直接遍历要更快。如果target存在于数组中，二分查找法找出来的下标返回即可；如果不存在于数组中，那么分为两种情况，一种是left等于right，这种情况在target比数组中最小值还小或者比数组中最大值还大的时候出现，这两种情况在函数一开始直接用if过滤掉就可以了；另一种情况就是left>right，这个时候通过写几个例子就可以发现应该要返回的是left。
代码如下：
class Solution {
public int searchInsert(int[] nums, int target) {
if(nums[0]>target){
return 0;
}
if(nums[nums.length-1]<target){
return nums.length;
}
int left=0,right=nums.length-1;
int mid=0,p=0;
while(right>=left){
mid=left+(right-left)/2;
if(nums[mid]<target){
left=mid+1;
}
else if(nums[mid]>target){
right=mid-1;
}
else{
p=mid;
break;
}
}
if(left>right){
p=left;
}
return p;
}
}
原文：https://www.cnblogs.com/xbc121/p/11733961.html