Binary Search glitches

[Ballaw]

Below is my first attempt at a binary search. It works for some numbers but for other it hops off into an infinite loop. All my attempts at debugging haven't helped. I'm too new at C++ to know what's going on. ANy help would be appreciated.


#include <iostream>

using namespace std;

void BinarySearch(int data[],int numElements, int searchKey) {
int lowerBound = 0, upperBound = numElements - 1, midpoint;
while (lowerBound < upperBound) {
midpoint = (upperBound + lowerBound) / 2;
if (data[midpoint] == searchKey) {
cout << searchKey << " is in position " << midpoint << endl;
break;
}
if (data[midpoint] < searchKey) {
upperBound = midpoint - 1;
}
if (data[midpoint] > searchKey) {
lowerBound = midpoint + 1;
}
}
if (upperBound < lowerBound) {
cout << searchKey << " not found." << endl;
}
};

int main()
{
int data[] = {1, 4, 5, 6, 9, 14, 21, 23, 28, 31, 42, 46, 50, 53, 57, 62, 63, 65, 74, 79, 89, 95};
int numElements = sizeof(data) / sizeof(int);
int key;
int x;

do {
cout << "Enter search key (or 'x' to exit): ";
cin >> key;
BinarySearch(data, numElements, key);
} while (key != x);
return 0;
}

[rollie]

The infinite loop isn't apparent to me, but consider one case in your search function: imagine the lower bound is 4 and the upper bound is 5. The midpoint becomes 4 (4+5 / 2), and then the lower bound increments to 5. What happens now? It's possible the value at index 5 matches your search key, and it's possible it doesn't. Will your function properly handle both cases? Or, to illustrate, think about what will happen if numElements is 1 (i.e., you are searching a list of size 1).

--Rollie