60. 搜索插入位置二分查找__细节
60. 搜索插入位置二分查找__细节
和蔼的zhxing
发布于 2018-09-04 11:33:25
发布于 2018-09-04 11:33:25
给定一个排序数组和一个目标值，如果在数组中找到目标值则返回索引。如果没有，返回到它将会被按顺序插入的位置。
你可以假设在数组中无重复元素。 样例
[1,3,5,6]，5 → 2
[1,3,5,6]，2 → 1
[1,3,5,6]， 7 → 4
[1,3,5,6]，0 → 0二分查找__细节
二分查找，找到了最好，找不到的话看情况插在哪里。
二分查找的while循环里的条件一定要写对，应该是beg<=end，等于号一定不要忘记了。
当遍历到beg和end相邻时：这时候计算出来的mid=beg。
如果是<，则下一次就直接跳出循环了。循环终止时，beg可能大于end也可能等于end。这样实际上是有一个值是没有遍历到的（就是当前的这个end）。
如果是<=，那么可能出现beg=end的情况，这种情况就是mid<target时。这个时候再进行一次循环，最后跳出循环肯定是beg=end+1。所以还是有细微的差别。
为了达到这种统一的循环终止状态，选择<=是合理的，终止状态肯定是beg=end+1，而且mid最终的位置，就是最后一次beg的位置。
这个位置的值如果大于target，那么应该插入到这个位置前面，如果小于的话，应该插入到后面。
int searchInsert(vector<int> &A, int target) {
if(A.empty()) //没有元素的特殊情况
return 0;
auto beg=A.begin();
auto end=A.end()-1;
vector<int>::iterator mid;
while(beg<=end)
{
mid=beg+(end-beg)/2;
if(*mid==target)
return mid-A.begin();
else if(*mid<target)
{
beg=mid+1;
}
else
end=mid-1;
}
if(*mid<target)
return mid-A.begin()+1;
if(*mid>target)
return mid-A.begin();
// write your code here
}本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2018.01.23 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录