java – 从Bentley的书(编程珍珠:编写正确的程序)修复二进制搜
发布时间:2020-12-14 16:33:09 所属栏目:Java 来源:网络整理
导读:二进制搜索可以通过许多方式实现 – 递归,迭代,条件等.我从Bentley的“编程珍珠:编写正确的程序”这个迭代实现中得到这个结果,其中包括一个错误. public class BinSearch { static int search( int [] A,int K ) { int l = 0; int u = A. length -1; int m;
二进制搜索可以通过许多方式实现 – 递归,迭代,条件等.我从Bentley的“编程珍珠:编写正确的程序”这个迭代实现中得到这个结果,其中包括一个错误.
public class BinSearch { static int search( int [] A,int K ) { int l = 0; int u = A. length -1; int m; while ( l <= u ) { m = (l+u) /2; if (A[m] < K){ l = m + 1; } else if (A[m] == K){ return m; } else { u = m-1; } } return -1; } } 我发现一个错误在行m =(l u)/ 2;它可能会导致溢出.这个二进制搜索怎么能避免这个溢出? 解决方法
尝试以下:
更改 m =(l u)/ 2 至 m =(u-1)/ 2l 如果您考虑了一个非常大的2 ^ 31 – 1个元素(有符号32位整数的最大值),则(l u)/ 2可以溢出的原因变得明显. 这样我们通过首先确定l和u(u-l)/ 2之间的相对中间位置来避免添加u,然后向其中加上较低的数字l,使其成为绝对的.所以在运行期间m =(u-1)/ 2 l;我们从不超过你的价值. 总结完整的代码: public class BinSearch { static int search( int [] A,int K ) { int l = 0; int u = A. length -1; int m; while ( l <= u ) { m = (u-l) / 2 + l; if (A[m] < K) l = m + 1; else if (A[m] == K) return m; else u = m - 1; } return -1; } } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |