c - 搜索功能只是有时有效

Question

我正在尝试制作二分查找功能，这是我当前的代码:

bool _search(int value, int values[], int start, int end);

/*
 * Main search function
 */
bool search(int value, int values[], int n) {
    if(value < 0)
            return false;
    sort(values, n);
    return _search(value, values, 0, n);
}

bool _search(int value, int values[], int start, int end) {
    if(start < end) {
        // get the mean for comparing
        int mean = (start + end) / 2;
        if(value == values[mean]) // middle
            return true;
        else if(value < values[mean]) // left half
            return _search(value, values, start, mean - 1);
        else // right half
            return _search(value, values, mean + 1, end);
    } else
        return false;
}

我将随机数传递给具有恒定种子的程序，如果我传递的数字数量为 861 或以下，它会正常工作。但是，如果它获得 862 或更高的数字，则无法找到值。诡异的。所以我尝试传递一个非常大的数字，比如 1862。它找到了!好吧……2000怎么样？没有。 3000？是的。 4000？没有。 5000？没有。 6000？是的。

这是怎么回事？

编辑:另外，如果数组只有 3 个元素，并且要搜索的元素是第一个元素，则不会找到它。算法肯定有问题，我就是不能指手画脚。

Answer 1

您的search 功能不正确:包含start，但应排除end。当你递归时，你不应该在 mean - 1 处停止，而是在 mean 处停止，否则，你会错过一些条目，并且搜索可能会在不应该的时候失败。

修改后的版本:

bool _search(int value, int values[], int start, int end) {
    if (start < end) {
        // get the mean for comparing
        int mean = (start + end) / 2;
        if (value == values[mean]) // middle
            return true;
        else
        if (value < values[mean]) // left half
            return _search(value, values, start, mean);
        else // right half
            return _search(value, values, mean + 1, end);
    } else {
        return false;
    }
}