CODEWITHSUNDEEP
c++for-loopwhile-loopbinary-search
ASHBRN-PHNX
ASHBRN-PHNX

Reputation: 133

Binary Search Function in C++ returns infinite loop

Alright, this is more a query so I can understand what this was doing, but, I have the below code. As is, the while loop would return an infinite loop, I change the while to a basic for(int i=0;i<n;i++) loop, it works and outputs correctly.

What is happening? I actually don't know why my while loop would get stuck but a for loop doesn't.

bool binary_search(const string A[], int n, string name, int &count){
   count = 0;                  // Count initialization
   int fst = 0;
   int lst = n+1;              // First, Last and Middle array elements
   int mid = 0;

   while(fst<=lst)
   {
      count++;

      mid = (fst+lst)/2;      // Calculate mid point of array
      if (A[mid]==name)       // If value is found at mid
      {
         return true;
      }
      else if (A[mid]>name)
      {                       // if value is in lower
         lst = mid++;
         //cout << "elseIfME!" << endl;
      }
      else if (A[mid]<name)
      {                       // if value is in higher
         fst = mid--;
         //cout << "elseME!" << endl;
      }
   }
   return false;

}

Upvotes: 2

Views: 1208

Answers (2)

user007
user007

Reputation: 2172

Your conditions shall look like this ::

// Assuming that the array you are searching is sorted in descending order
// and hence the else-if conditions
else if (A[mid]>name)
{                       
   lst = mid + 1;
}
else if (A[mid]<name)
{      
   fst = mid - 1;
}

The post increment you are using is useless! Since, when you post increment (mid++ and mid--), it returns the original value (mid), and then the value is incremented/decremented, so actually, you set fst = mid and lst = mid in your code every time you do not find the element.

So, what happens is when fst = lst when during binary search you have shortened your domain of search in the array to just 1 element, you calculate mid which comes equal to fst and lst, and if the element is not found, you either assign fst = mid or lst = mid, since this is where your loop is supposed to stop, and to stop the condition fst <= lst shall be violated, which is not, and hence the infinite loop.

Even during the search when you are narrowing down your search domain by comparing the center element, you have to exclude the center element you just compared, which you do not because of the post increment!

You can use pre-increment and pre-decrement as well if you want it to work! (++mid and --mid)

Upvotes: 6

DBug
DBug

Reputation: 2566

I think your logic is backwards. if (A[mid]>name) is true, then name is in the lower half of the list, but you're increasing mid past this point, into a portion of list that it can't be in. In this case you should set lst = mid-1, not mid--, since that sets lst to mid, THEN decrements it. Same for test if (A[mid]<name), you should set fst = mid + 1, like:

  else if (A[mid]>name)
  {                       // if value is in lower
     lst = mid - 1;
     //cout << "elseIfME!" << endl;
  }
  else if (A[mid]<name)
  {                       // if value is in higher
     fst = mid + 1;
     //cout << "elseME!" << endl;
  }

Basically, your original logic, when it determines the portion of the list that the value should be in, increases the size of this portion, instead of shortening it, so you just keep searching larger sublists, not smaller ones.

Upvotes: 2

Related Questions