首页 > 技术文章 > 自己犯得错---二分查找

LittleMore 2015-01-05 22:28 原文

 二分查找都好难啊... 路途漫漫兮。没看书之前自己第一遍的实现,循环的终止条件是仅仅判断mid值是否落在区间内。当然这个是错误的,而且比较愚蠢。

第二次 查了下网上的实现后 把循环的判读条件改成了while(l < h) ,循环外直接return -1;对于我的实现,又犯了一个错误,这种条件下会少比较一个元素,就是少比较 l = h 时 指向的元素。

最后我把 循环条件改成了 while(l <= h) 才没有测试出错。

不过可能我的测试用例可能没有覆盖完全,明天再继续论证下。

二分查找还要一个重要的易错点是 整数加法的溢出... 不知道这世上有多少的bug是出在溢出上,一定要多留心眼。

书上给出的解决方案是 mid = l + ((h - l)>> 1); 

就是数学公式 (a + b) / 2 = b + (b - a) / 2 得应用。

 

推荐阅读