CODEWITHSUNDEEP
c++infinite-loopbinary-search
krizzo
krizzo

Reputation: 1883

Binary search stuck infinite loop?

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;
    }
}

Upvotes: 2

Views: 3604

Answers (3)

Adrian McCarthy
Adrian McCarthy

Reputation: 48019

I believe:

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

should be:

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

I'd probably add:

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

Also, the:

return false;

should be after the loop. Once you've checked <, and >, the only possible result left is == (with ints), so that final else clause will never hit. (If you were using a floating point type for the index, then you can get some weird situations with NaNs, infinities, and maybe negative zeroes.)

Turn up the warning level on your compiler. It should have warned you about the unreachable code and the path without a return.

Upvotes: 9

twalberg
twalberg

Reputation: 62479

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.

Upvotes: 2

Maxim Egorushkin
Maxim Egorushkin

Reputation: 136495

This:

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

Should probably be:

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

Or simply the average:

mid = (upper + lower) / 2;

Upvotes: 3

Related Questions