C++: Why does my binary search function run into an infinite loop?

Question

I am having a bit of trouble with creating a Binary Search using a templated dynamic array class and iterators. In my class I have the following function that causes an infinite loop.

iterator binarySearch(const T& value)
 {
 T * indexOfFirst = begin();
 T * indexOfLast = (end() - 1);
 size_t tempSize = m_size;
 while (indexOfFirst <= indexOfLast) 
 {
 tempSize = (tempSize / 2);
 T * indexOfMiddle = ((m_array) + tempSize);

 if (value > *indexOfMiddle)

{
 indexOfFirst = (indexOfMiddle + 1);
 }
 else if (value < *indexOfMiddle)
 {
 indexOfLast = (indexOfMiddle - 1);
 }
 else
 {
 return (indexOfMiddle - 1);
 }
 }
 return (end());
 } 

In my main function, I am using the following code to test the binary search. Currently, I'm using an array of integers to perform the test. My array is: {2, 4, 6, 8, 32, 64, 128}.

int * end = array.end();
int * searcher = array.binarySearch(8);
 if (searcher != end)
 {
 cout << "found in element: " << (searcher - array.begin()) << endl;
 }
 else
 {
 cout << "not found";
 }

As you can see, the number 8 is in the array. However, my search just runs into a loop. If I switch the array to be {2, 4, 8, 16, 32}, then it reports back that it found the number 8. Any help would be much appreciated. Thank you in advance. I know there is something wrong with the logic of my search, but I just can't track it down.

• GManNickG: I hope your code isn't actually formatted like that. :)
• James McNellis: If you step through the function (using a debugger or simple "printf-debugging") you should see that it either gets stuck on a single set of extents without narrowing them or it starts alternating between two sets of extents. Once you figure out which of those it is it is usually straightforward to figure out what is causing the problem.
• Arun: @GMan: I think its time to introduce a button (like the 101-010 for marking a section of text as code) for pretty formatting and indenting :)
• JoshD: @ArunShaha: Oh, man! What a great idea. We could even add a keyboard shortcut like CTRL-k or something :)

Answer 1

Its no fun if someone else does your homework, but I'll offer a suggestion. If you cout all the key variables right after

while (indexOfFirst <= indexOfLast) 

I bet you anything you'll see the problem immediately.