我执行二分查找的代码哪里出错了？

Question

我正在为二分搜索算法编写代码。

代码：

#include "cs50.h"

int main(void) {
    int n = GetInt();
    int value = GetInt();
    int values[n];

    for (int i = 0; i < n; i++) {
        printf("Put in number %i ", i + 1);
        values[i] = GetInt();
    }

    int mid = (n - 1) / 2;
    int en = 0;
    int ex = n - 1;

    for (int i = 0, xt = i + 1; i < xt; i++) {
        if (value > values[mid]) {
            en = mid;
            mid = (en + ex) / 2;
        }
        else if (value < values[mid]) {
            ex = mid;
            mid = (en + ex) / 2;
        }
        else if (value == values[mid]) {
            printf("found");
            break;
        } else {
            printf("not found");
            break;
        }
    }
}

但它仅在要查找的值位于中间某个位置时才有效。

当出现以下情况时会失败：

1. 要找到的值是第一个或最后一个。
2. 要查找的值不在输入的值中。

我实在无法找出其中的错误。

Answer 1

在二分搜索中，有很多小事情你必须做对：处理 length=0 的情况，确保你测试的位置始终有效，确保你不会溢出（即，`(low+high) /2' 不是最好的写法），确保新的测试位置始终与前一个不同，等等。

在完成了一百万次之后，我编写的每个二分搜索现在都是这样完成的：

bool search(int array[], int length, int valueToFind)
{
    int pos = 0;
    int limit = length;
    while(pos < limit)
    {
        int testpos = pos + ((limit - pos) >> 1);

        if (array[testpos] < valueToFind)
            pos = testpos + 1;
        else
            limit = testpos;
    }
    return (pos < length && array[pos] == valueToFind);
}

请注意，每次迭代我们只需要进行一次比较，这比其他答案中的搜索要快。我们不是在循环内进行相等性测试，而是可靠地找到要查找的元素所属的位置，每次迭代仅使用一次比较，然后在最后测试以查看我们想要的元素是否在那里。

我们的计算方式testpos确保pos <= testpos < limit, AND 即使长度是最大可能的整数值，它也能工作。

这种形式还使得您可以很容易地读出您想要看到的不变量，而不必考虑奇怪的边界条件，例如high<low。当你从循环中出来时，pos==limit这样你就不用担心用错了等等。

此循环中的条件也很容易适应不同目的的二分搜索，例如“查找插入 x 的位置，确保它位于数组中已有的所有 x”、“查找数组中的第一个x”、“找到数组中的最后一个x”，等等。