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; }
I’m pretty confused by this, what’s wrong?
Advertisement
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.