Binary Search Function in C++ returns infinite loop

Question

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;
}

• Jarod42: you post increment/decrement when assigning to fst/lst is useless.

Answer 1

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)

• ASHBRN-PHNX: Ah, so I guess mid++ <- the "++" is best used for loops, so for situations where the value is only being checked and applied once (as is in if) I would need to make sure it's mid + 1?
• user007: @pacificfrost Its nothing like its best for the loop or anything, you just need to be sure when the value will be updated, like, even when using post increment you can write mid++; lst = mid because when you come at the next statement after the increment, mid has been updated and it will work, it just depends on what you want to be done!
• ASHBRN-PHNX: Ah. I understand now. Thank you! I'm going to play with this concept once I'm done in class and hopefully once I've played with it I can fix the while loop to work for me.

Answer 2

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.

• user007: @Jarod42 The question doesn't mention if the array is sorted in ascending or descending order!
• ASHBRN-PHNX: Thank you! I really appreciate the explanation!
• ASHBRN-PHNX: And also, I validated it because for me it was a little more clear, I understood the explanation more and it also answered what I was trying to ask.