c语言 - 当数组中有超过 44 个元素时，二进制搜索停止工作

Question

这是我第一次在这里发帖，所以如果发生这种情况，请原谅愚蠢的错误。

我是 C 编码的初学者(现在正在学习)，坦率地说，我不是数学天才，所以我遇到的问题让我很困惑。我通过测试不同的东西找到了解决方案，但老实说，我不完全明白为什么我的解决方案确实有效，而应用解决方案之前的代码不起作用。

该代码是使用种子 srand48 创建的排序数组中给定数字的二进制搜索，并使用线性排序进行排序。

来框定情况。解决方案之前的代码确实运行良好，直到数组达到 45 个元素，然后它停止查找数字。

在解决方案代码之前：

bool search(int value, int values[], int n)
{
int first, middle, last;
first = 0;
last = n - 1;
middle = (first + last) / 2;
if (n > 0)
{
while (first < last)
{
if (values[middle] == value)
{
return true;
}
else if (values[middle] < value)
{
first = middle + 1;
}
else
{
last = middle - 1;
}
middle = (first + last) / 2;
}
}
else
{
return false;
}
return 0;
}

我找到的解决方案只是从新的中间值分配中删除 + 和 - 1。在我这样做之后，它工作得很好。我想知道的是，对于我自己未来的参考和学习，为什么第一个代码不起作用，以及为什么该解决方案修复了它。(我可能会以某种方式下意识地理解这是如何工作的，这就是我想出修复方法的原因，但我无法有意识地弄清楚它背后的逻辑。

Answer 1

代码中存在一些细微的问题：

• 如果数组只有一个元素，它不起作用：它将始终返回0。这个问题实际上是导致你观察到的行为：你测试while (first < last)但first和last都包含在搜索范围内。 您应该使用while (first <= last)或更改算法以排除last，我赞成，因为您不再需要使用此解决方案对空数组进行特殊处理。

• 如果失败，它可以返回false或0，这在 C 中是可以的，但在 javascript 中是不同的。应删除else子句。

• 如果n大于最大值的一半，则middle的计算具有潜在的算术溢出，如果int并且value足够大。 这实际上是一个经典的错误，在许多标准 C 库中隐藏了很多年。 而不是middle = (first + last) / 2，你应该使用：

  middle = first + (last - first) / 2;
  

以下是更正和简化的版本：

bool search(int value, int values[], int n) {
int first = 0, last = n;
while (first < last) {
int middle = first + (last - first) / 2;
if (values[middle] == value) {
return true;
}
if (values[middle] < value) {
first = middle + 1;
} else {
last = middle;
}
}
return false;
}

请注意，如果数组中存在重复项，则找到value的middle值不一定是 中出现的最小索引。 这不是问题，因为您只对布尔结果感兴趣，但是如果要找到最小的索引，则必须更改算法。

Matt Timmermans在另一个问题中发布了一个更好的算法，它既更有效又具有这个属性：

bool search(int value, int values[], int n) {
int pos = 0;
int limit = n;
while (pos < limit) {
int middle = pos + ((limit - pos) >> 1);
if (values[middle] < value)
pos = middle + 1;
else
limit = middle;
}
return pos < n && values[pos] == value;
}

至于你的最后一个问题：为什么从代码中删除+ 1和-1可以解决问题？您的修复无法完全纠正问题：您的更改会产生以下效果：

• first = middle;只是次优的，搜索将花费更长的时间，但没有其他效果。
• last = middle;修复了这个问题，因为循环假定last被排除，这与last = middle;一致。
• 剩下的问题是last的初始值，应该last = n;。
使用last = n - 1;，如果该值
• 位于数组的末尾而没有重复项，则仍然无法找到该值，包括如果数组只有一个元素。