当数组中的元素超过 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

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

如果数组只有一个元素则不起作用：它将始终 return 0。这个问题实际上是导致您观察到的行为：您测试 while (first < last) 但 first 和 last 都包含在要搜索的范围内。您应该使用 while (first <= last) 或更改算法以排除 last，我赞成这样做，因为您不再需要使用此解决方案对空数组进行特殊处理。
失败时可以returnfalse或0，这在C中是可以的，但在javascript中不同。您应该删除 else 子句。
如果 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;
}

请注意，如果数组中有重复项，则找到 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;，如果值位于数组的末尾且没有重复项，您仍然无法定位该值，包括如果数组只有一个元素。

当数组中的元素超过 44 个时，二进制搜索将停止工作

Binary search stops working when more than 44 elements in an array

c

arrays

binary-search