首页 文章

二进制搜索卡住无限循环？

提问于
浏览 次
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;
    }
}
c++ infinite-loop binary-search

3 回答

  • 2

    我相信：

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

    应该：

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

    我可能会补充：

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

    另外，：

    return false;

    应该在循环之后 . 一旦你检查了 < 和 > ，剩下的唯一可能的结果是 == （带有整数），所以最终的 else 子句永远不会被击中 . （如果你使用浮点类型作为索引，那么你可以得到一些奇怪的情况，包括NaN，无穷大，也许是负零 . ）

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

    回复于
  • 9

    这个：

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

    应该是：

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

    或者只是平均值：

    mid = (upper + lower) / 2;
    回复于
  • 3

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

    回复于

相关问题