CODEWITHSUNDEEP
c++
Lord_Dizzie
Lord_Dizzie

Reputation: 37

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

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.

Upvotes: 0

Views: 495

Answers (1)

Scott Stafford
Scott Stafford

Reputation: 44818

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.

Upvotes: 2

Related Questions