2

我创建了这个二分搜索,但似乎每次都陷入循环。它所检查的只是一个向量。我不知道我需要改变什么,我尝试了很多不同的东西。

[1,2,4,6] 如果我搜索 4 永远不会找到它不断击中下 = 中 + 1。

bool SortSearch::binarySearcher(int size, int val)
{
    int lower = 0, upper = size - 1, mid;

    while (lower < upper)
    {
        mid = (lower + (upper-lower))/2;
        if (students[mid].getID() > val)
            upper = mid - 1;
        else if (students[mid].getID() < val)
            lower = mid + 1;
        else if (students[mid].getID() == val)
            return true;
        else
            return false;
    }
}
4

3 回答 3

9

我相信:

mid = (lower + (upper-lower))/2;

应该:

mid = lower + (upper-lower)/2;

我可能会补充:

assert(lower <= mid && mid <= upper);

此外,该:

return false;

应该在循环之后。一旦你检查了<, 和>,剩下的唯一可能的结果就是==(with ints),所以最后的else子句永远不会命中。(如果您使用浮点类型作为索引,那么您可能会遇到一些奇怪的情况,包括 NaN、无穷大,甚至可能是负零。)

调高编译器的警告级别。它应该警告您有关无法访问的代码和没有返回的路径。

于 2012-05-21T16:25:56.360 回答
3

这个:

mid = (lower + (upper-lower))/2;

应该是:

mid = lower + (upper-lower) / 2;

或者只是平均值:

mid = (upper + lower) / 2;
于 2012-05-21T16:26:48.517 回答
2

在每次迭代中打印lowerupper和的值可能很有启发性。mid考虑当lowerupper仅相差 1 时会发生什么 - thenmid将被计算为等于lower,这意味着在下一次迭代中lower并且upper将与上一次迭代相同,从而导致无限循环条件。

于 2012-05-21T16:31:37.870 回答