二进制搜索可以通过许多方式实现 – 递归,迭代,条件等.我从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 =(u-1)/ 2l
如果您考虑了一个非常大的2 ^ 31 – 1个元素(有符号32位整数的最大值),则(l u)/ 2可以溢出的原因变得明显.
在这种情况下,第一次迭代是很好的,因为2 ^ 31 – 1 0并不是很大的,但在这里考虑l = m 1的情况.在第二次迭代中,u仍然是相同的,l是2 ^ 31/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;
}
}
