AcWing
  • 首页
  • 课程
  • 题库
  • 更多
    • 竞赛
    • 题解
    • 分享
    • 问答
    • 应用
    • 校园
  • 关闭
    历史记录
    清除记录
    猜你想搜
    AcWing热点
  • App
  • 登录/注册

二分边界详细总结

作者: 作者的头像   T-SHLoRk ,  2019-07-10 01:24:53 ,  所有人可见 ,  阅读 4946


47


67

二分查找模板

一、查找精确值

从一个有序数组中找到一个符合要求的精确值(如猜数游戏)。如查找值为Key的元素下标,不存在返回-1。

//这里是left<=right。
//考虑这种情况:如果最后剩下A[i]和A[i+1](这也是最容易导致导致死循环的情况)首先mid = i,
//如果A[mid] < key,那么left = mid+1 = i +1,如果是小于号,则A[i + 1]不会被检查,导致错误
int left = 1,right = n;
while(left <= right)
{
   //这里left和right代表的是数组下标,所有没有必要改写成mid = left + (right - left)/2;
  //因为当代表数组下标的时候,在数值越界之前,内存可能就已经越界了
  //如果left和right代表的是一个整数,就有必要使用后面一种写法防止整数越界
        int mid = (left + right) / 2;
    if(A[mid] == key)
      return mid;
    else if(A[mid] > key)//这里因为mid不可能是答案了,所以搜索范围都需要将mid排除
      right = mid - 1;
    else
      left = mid + 1;
}
return -1;

二、查找大于等于/大于key的第一个元素

这种通常题目描述为满足某种情况的最小的元素。

int left = 1,right = n;
while(left < right)
{
  //这里不需要加1。我们考虑如下的情况,最后只剩下A[i],A[i + 1]。
  //首先mid = i,如果A[mid] > key,那么right = left = i,跳出循环,如果A[mid] < key,left = right = i + 1跳出循环,所有不会死循环。
  int mid = (left + right) / 2;
  if(A[mid] > key)//如果要求大于等于可以加上等于,也可以是check(A[mid])
    right = mid;
  //因为找的是大于key的第一个元素,那么比A[mid]大的元素肯定不是第一个大于key的元素,因为A[mid]已经大于key了,所以把mid+1到后面的排除
  else
    left = mid + 1;
  //如果A[mid]小于key的话,那么A[mid]以及比A[mid]小的数都需要排除,因为他们都小于key。不可能是第一个大于等于key的元素,
}

三、查找小于等于/小于key的最后一个元素

这种通常题目描述为满足某种情况的最大的元素。如Leetcode69题,求sqrt(x)向下取整就是这种模板。

int left = 1, right = n;
while(left < right)
{
  //这里mid = (left + right + 1) / 2;
  //考虑如下一种情况,最后只剩下A[i],A[i + 1],如果不加1,那么mid = i,如果A[mid] < key,执行更新操作后,left = mid,right = mid + 1,就会是死循环。
  //加上1后,mid = i + 1,如果A[mid] < key,那么left = right = mid + 1,跳出循环。如果A[mid] > key,left = mid = i,跳出循环。
  int mid = (left + right + 1) / 2;
  if(A[mid] < key)
    left = mid;//如果A[mid]小于key,说明比A[mid]更小的数肯定不是小于key的最大的元素了,所以要排除mid之前的所有元素
  else
    right = mid - 1;//如果A[mid]大于key,那么说明A[mid]以及比A[mid]还要大的数都不可能小于key,所以排除A[mid]及其之后的元素。
}

四、总结

最后两种情况的循环跳出条件是left<right,为什么不是小于等于呢?因为我们的区间变换思路是不断的舍去不可能是解的区间,最后只剩下一个数就是我们的解。而第一种情况就算最后只剩一个数也有可能不是解,所以需要使用小于等于。

  • 查找精确值,循环条件是小于等于;查找满足情况的最大最小值,循环条件是小于。
  • 查找满足条件的最大数,mid = (right + left + 1) / 2;查找满足条件的最小数,mid = (right + left)/2
  • mid = left + (right - left) / 2,不是适用于所有的情况。
  • 如果存在没有解的情况,比如从[1,2,3,4,5]找出大于等于6的第一个数,我们只需要将最后剩下的数单独进行一次判断就可以了。

13 评论


用户头像
刚果金   2022-07-28 12:00         踩      回复

非常不错


用户头像
码   2021-08-17 22:21         踩      回复

这里是不是写错了//考虑如下一种情况,最后只剩下A[i],A[i + 1],如果不加1,那么mid = i,如果A[mid] < key,执行更新操作后,left = mid,right = mid + 1,就会是死循环。 //加上1后,mid = i + 1,如果A[mid] < key,那么left = right = mid + 1,跳出循环。如果A[mid] > key,left = mid = i,跳出循环。不应该是如果A[mid] > key,left = mid = i+1么


用户头像
aboutb1ank   2021-05-05 17:51         踩      回复

那我如果要查找小于等于/小于key的第一个元素
while(left < right)
{

int mid = (left + right) / 2;
if(A[mid] <= key)
right = mid;
else
left = mid + 1;
}

是这样吗


用户头像
junxiang   2019-07-12 22:22         踩      回复

分开记容易迷,我觉得后两张情况还是left <= right 更容易记,这样循环break的时候left=right+1,可以根据选大还是选小返回left或者right.

用户头像
T-SHLoRk   2019-07-12 22:48         踩      回复

嗯嗯,是的。主要是能理解三种不同情况的区别就可以了。主要理解的是二分的区间变换就是不断排除不可行的区间,保留潜在的可行区间就可以。


用户头像
emilyusa   2019-07-10 10:00         踩      回复

谢谢楼主,配合第一周的打卡练习非常好。

用户头像
T-SHLoRk   2019-07-10 10:41         踩      回复

共同进步

用户头像
TK   2019-07-12 18:29    回复了 T-SHLoRk 的评论         踩      回复

楼主能配例子吗,为什么第一个模板解不了LeetCode 33. Search in Rotated Sorted Array ?

用户头像
T-SHLoRk   2019-07-12 21:52    回复了 TK 的评论         踩      回复

可以看我刚刚写的第33题的题解。
https://www.acwing.com/solution/leetcode/content/2790/

用户头像
T-SHLoRk   2019-07-13 23:53    回复了 TK 的评论         踩      回复

更新了Search in Rotated Sorted Array 2题解,可以参考一下
https://www.acwing.com/solution/LeetCode/content/2815/

用户头像
TK   2019-07-16 22:37    回复了 T-SHLoRk 的评论         踩      回复

谢谢楼主的回复!

用户头像
TK   2019-07-16 22:38    回复了 T-SHLoRk 的评论         踩      回复

感觉看了老师的第一期leetcode解答很有启发,还是严格套用老师的模板方便,这样不用思考很多边界的问题

用户头像
T-SHLoRk   2019-07-17 00:14    回复了 TK 的评论         踩      回复

对的,我的模板就是根据老师的来写的,只不过写了每一步为什么要这么做。大神多年的经验肯定是我们比不上的。多多学习就完事了。


App 内打开
你确定删除吗?
1024
x

© 2018-2025 AcWing 版权所有  |  京ICP备2021015969号-2
用户协议  |  隐私政策  |  常见问题  |  联系我们
AcWing
请输入登录信息
更多登录方式: 微信图标 qq图标 qq图标
请输入绑定的邮箱地址
请输入注册信息