这是我第一次在这里发帖，如果发生这种愚蠢的错误，请原谅。
我是 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。在我这样做之后，它工作得很好。我想知道的是我自己 future 的引用和学习是为什么第一个代码不起作用，为什么那个解决方案修复了它。 (我可能不知何故下意识地理解这是如何工作的，这就是我想出解决办法的原因，但我无法有意识地弄清楚它背后的逻辑。)
您的代码中存在一些细微的问题:
如果数组只有一个元素则不起作用:它将始终返回 0 .这个问题实际上是导致您观察到的行为:您测试 while (first < last)但是first和 last都包含在要搜索的范围内。您应该使用 while (first <= last)或更改算法以排除 last ，我赞成，因为您不再需要使用此解决方案对空数组进行特殊处理。
它可以返回false或 0万一失败，这在 C 中是可以的，但在 javascript 中是不同的。您应该删除 else条款。
middle 的计算如果 n 有潜在的算术溢出如果 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;
}
请注意 middle值在哪里 value如果数组中有重复项，则 was found 不一定是出现 is 的最小索引。这不是问题，因为您只对 bool 结果感兴趣，但如果您想找到最小索引，则必须更改算法。
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; ，如果该值位于数组末尾且没有重复值，您仍然无法找到该值，包括如果该数组只有一个元素。