Buggy simple function for binary search (C++)

I wrote a simple function for binary search, but it’s not working as expected. I have a vector with 4000000 32-bit ints. Usually, when I search for a number, if it’s there, it’s found and the index is returned, if it’s not, -1 is returned (the index always corresponds to the value, but that’s not the point).

While messing around with the program I found out that it can’t find 93 (even though it’s there), obviously, there must be more values it can’t find.

I use CLion, which implements GDB as the debugger and G++ as the compiler.

template<typename T>
int BinarySearch(vector<T>& vec, T& request)
{

    int low = 0;
    int high = vec.size() - 1;

    while (low < high)
    {
        int mid = (low / 2 ) + (high / 2); // Styled it this way to avoid overflows. 
// This looks like where the bug happens, basically low and high both 
// become 93 while mid becomes 92,
// it then exits the loop and returns -1 because low is not lower than
// high anymore.

        if (vec[mid] == request)
        {
            return mid;
        }
        else if (vec[mid] < request)
        {
            low = mid + 1;
        }
        else if (vec[mid] > request)
        {
            high = mid - 1;
        }

    }
    return - 1;

}

JavaScript
​x
 
template<typename T>int BinarySearch(vector<T>& vec, T& request){​    int low = 0;    int high = vec.size() - 1;​    while (low < high)    {        int mid = (low / 2 ) + (high / 2); // Styled it this way to avoid overflows. // This looks like where the bug happens, basically low and high both // become 93 while mid becomes 92,// it then exits the loop and returns -1 because low is not lower than// high anymore.​        if (vec[mid] == request)        {            return mid;        }        else if (vec[mid] < request)        {            low = mid + 1;        }        else if (vec[mid] > request)        {            high = mid - 1;        }​    }    return - 1;​}​

I’m pretty confused by this, what’s wrong?

Answer

Condition should be while (low <= high).

If you keep it as while (low < high), then when low==high (means we reach the final element), while loop will break and will return -1. So,your program wont check that element.

Also you should use mid=low+(high-low)/2; to prevent overflow and access all values.
Problem in your code is that suppose when low=high=1, it will give mid =0(due to data conversion), which is wrong.

Advertisement

Answer