原文:
考虑下面 c 实现的功能，这里面有什么不对吗？
// a iterative binary search function. it returns location of x in
// given array arr[l..r] if present, otherwise -1
int binarysearch(int arr[], int l, int r, int x)
{
while (l <= r)
{
// find index of middle element
int m = (l r)/2;
// check if x is present at mid
if (arr[m] == x) return m;
// if x greater, ignore left half
if (arr[m] < x) l = m 1;
// if x is smaller, ignore right half
else r = m - 1;
}
// if we reach here, then element was not present
return -1;
}
上面看起来很好，除了一个微妙的东西，表达式“m = (l r)/2”。对于较大的 l 和 r 值，它会失败。具体来说，如果低和高的总和大于最大正 int 值(231–1)，它会失败。总和溢出为负值，该值除以 2 后仍为负值。在 c 语言中，这会导致数组索引超出界限，并产生不可预测的结果。
解决这个问题的方法是什么？ 以下是一种方式:
int mid = low ((high - low) / 2);
可能更快，可以说很清楚(只在 java 中起作用，参考):
int mid = (low high) >>> 1;
在 c 和 c 中(这里没有>>>运算符)，您可以这样做:
mid = ((unsigned int)low (unsigned int)high)) >> 1
类似的问题也出现在中。
以上内容摘自。
也请参考，它指出上述pg电子试玩链接的解决方案可能并不总是有效的。
当数组长度为 2 30 或更大，并且搜索重复移动到数组的后半部分时，会出现上述问题。这么大的数组不太可能在大多数时候出现。例如，当我们用 32 位编译器尝试下面的程序时，我们会得到编译器错误。
int main()
{
int arr[1<<30];
return 0;
}
输出:
error: size of array 'arr' is too large
即使我们尝试布尔数组，程序也能很好地编译，但是在 windows 7.0 和 32 位编译器中运行时会崩溃
#include
int main()
{
bool arr[1<<30];
return 0;
}
输出:没有编译器错误，但在运行时崩溃。
来源:
本文由阿沛·拉提供稿。如果您发现任何不正确的地方，或者您想分享更多关于上面讨论的主题的信息，请写评论
麻将胡了pg电子网站的版权属于：月萌api www.moonapi.com，转载请注明出处
