首页 > 代码库 > 自己犯得错---二分查找
自己犯得错---二分查找
二分查找都好难啊... 路途漫漫兮。没看书之前自己第一遍的实现,循环的终止条件是仅仅判断mid值是否落在区间内。当然这个是错误的,而且比较愚蠢。
第二次 查了下网上的实现后 把循环的判读条件改成了while(l < h) ,循环外直接return -1;对于我的实现,又犯了一个错误,这种条件下会少比较一个元素,就是少比较 l = h 时 指向的元素。
最后我把 循环条件改成了 while(l <= h) 才没有测试出错。
不过可能我的测试用例可能没有覆盖完全,明天再继续论证下。
二分查找还要一个重要的易错点是 整数加法的溢出... 不知道这世上有多少的bug是出在溢出上,一定要多留心眼。
书上给出的解决方案是 mid = l + ((h - l)>> 1);
就是数学公式 (a + b) / 2 = b + (b - a) / 2 得应用。
自己犯得错---二分查找
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。