Binary search stuck infinite loop?

Question

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

Answer 1

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.