题目
题目链接
分析
大家都知道二分查找其实有很多种写法，这里一个比较巧妙地点就是，这个写法可以在返回插入位置的时候直接返回i，不用进行处理。
那么为什么这种写法可以呢？ 我们来分析一下，首先我们的写法是：
- 当target不等于nums[mid]时，我们选择了i=mid+1,j=mid-1
- while循环结束条件是i>j
举例分析：如果我们的输入是 1 3 4 5 2文章来源：https://www.toymoban.com/news/detail-508013.html
- i=0，j=3，mid=1，因为3>2，因此j=mid-1=0
- while循环没有结束，继续。
- i=0，j=0，mid=0，因为1<2，因此i=mid+1=1
- i>j，while循环结束
可以看到当target不存在于数组中时，会以nums[i]<target，i=mid+1>j结束循环，nums[i]就是刚好小于target的那个数字，而nums[i+1]就是大于target的数字。文章来源地址https://www.toymoban.com/news/detail-508013.html
AC代码
class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
int i=0;
int j=nums.size()-1;
while(i<=j){
int mid=(i+j)/2;
if(nums[mid]==target){
return mid;
}
else if(nums[mid]<target){
i=mid+1;
}
else if(nums[mid]>target){
j=mid-1;
}
}
return i;//返回插入的位置
}
};
到了这里，关于leecode-二分查找的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
