二分法浅谈

举报
陈沧夜 发表于 2022/05/01 22:44:56 2022/05/01
【摘要】 文章目录 前言循环条件?当循环条件为 < 时当循环条件为 <= 时 搜索的区间如何定义?溢出如何解决? 前言 最近在做力扣的 14 天计划 「算法」 - 学习计划 -...

前言

最近在做力扣的 14 天计划 「算法」 - 学习计划 - 力扣(LeetCode)全球极客挚爱的技术成长平台 (leetcode-cn.com)

然后第一天就是 二分查找

704. 二分查找 - 力扣(LeetCode) (leetcode-cn.com)

278. 第一个错误的版本 - 力扣(LeetCode) (leetcode-cn.com)

35. 搜索插入位置 - 力扣(LeetCode) (leetcode-cn.com)

虽然题目难度不大,但是还是得惊呼一声好家伙

然后发现了之前长期未解决并暴露的问题:

什么时候用left<right?什么时候用left<=right?

搜索的区间如何定义?

(left+right)/2 溢出如何解决?

循环条件?

当循环条件为 < 时

循环跳出后所得的结果为 left == right 。这时候,left 与 right 就夹出了唯一的位置,这个位置就是目标值的位置,或者说是如果这个元素存在,应该在的位置。更值得一提的是, left == right 时,返回 left,right 都行,因为它两值相等。因此可以判断元素存在时的位置。

当循环条件为 <= 时

循环跳出后所得的结果为 left > right 。这时候,left 与 right 就走过头了,此时就表明该元素不存在。因此可以判断元素存不存在

搜索的区间如何定义?

初始区间应该能够覆盖到所有可能返回的结果。下界是 0 是显然的,但是上界是 n 还是 n-1 取决于元素可不可能比所有序列中元素都大?都大则为 n

溢出如何解决?

mid = left + (right - left)/2 可以避免溢出

文章来源: blog.csdn.net,作者:沧夜2021,版权归原作者所有,如需转载,请联系作者。

原文链接:blog.csdn.net/CANGYE0504/article/details/119921601

【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。