2

I created this binary search but it seems to get stuck in a loop each time. All it's checking is a vector. I'm stuck as to what I need to change I've tried so many different things.

[1,2,4,6] if I search for 4 is never is found it keeps hitting the lower = mid + 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;

ループの後にある必要があります。、、をチェック<すると>、残っている可能性のある結果は==（intを使用）のみであるため、finalelse句がヒットすることはありません。（インデックスに浮動小数点型を使用していた場合、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

It might be illuminating to print the values of lower, upper, and mid on each iteration. Consider what happens when lower and upper only differ by 1 - then mid will be calculated to be equal to lower, which means on the next iteration that lower and upper will be identical to the previous iteration, leading to an infinite loop condition.

于 2012-05-21T16:31:37.870 に答える