Function only returns true, why?!

[taymaxi]

I'm trying to perform a binary search on a sorted vector for a homework assignment, but it's not working.

These are my two functions which compare entries:

bool PhoneEntry::equalAlpha(const PhoneEntry &param){
	bool equal = false;

	cout << "NAMES: " << lastName << " " << param.lastName << endl;
	if (lastName == param.lastName && firstName == param.firstName){
			equal=true;}

	return(equal);
}

bool PhoneEntry::greaterAlpha(const PhoneEntry& param) {
	bool longer = false;

	if (lastName > param.lastName)
		longer = true;
	else if (lastName == param.lastName){
		if (firstName > param.firstName){
			longer=true;}}

	return(longer);
}

int binarySearch(PhoneEntry &keyP, const vector<PhoneEntry> &entryNames)
{
	int low = 0, 
		high = entryNames.size()-1, 
		mid = (low + high) / 2;

	while (low <= high)
	{		
		if (keyP.equalAlpha(entryNames[mid]))
			break;
		mid = (low + high) / 2;
		if (keyP.greaterAlpha(entryNames[mid]))
			high = mid - 1; //this ALWAYS evaluates to true in the search!
		else if (!keyP.greaterAlpha(entryNames[mid]))
			low = mid + 1;
	}

	if (keyP.equalAlpha(entryNames[mid]))
		return mid;
	else
		return (mid * -1);
};

I know that greaterAlpha works because I use it to successfully sort the vector in another function, so I don't understand why it keep returning true. Doing that causes it to just drive mid down to 0 and return the very first entry in the vector each time.

(I'm sorry if this post is unclear at all, if you need any more parts of the program I can include them. I tried to simplify this post by only including the vital parts, but I'm new to this so I'm not even sure what all the vital parts are, sorry)

Thanks in advance!

[clanmjc]

Have you place a break point in the function? Step through when it should be false but returns true?

[cire]

You are updating mid in the wrong place. It either needs to be at the top of the loop or the bottom of the loop. If you have it in the middle of the loop, equalAlpha and greaterAlpha are working on different elements.

[taymaxi]

I have a break function at line 10 in the binarySearch function.

I declare mid as (low + high)/2 and then test it at the start of the while loop before updating it so that I can test the middle element, just in case that happens to be the one I'm looking for. If I don't, the middle element never gets tested. I test the updated mid at the beginning of the next iteration and break if it's the one I want, then again outside the loop to return the value of mid.

[cire]

I test the updated mid at the beginning of the next iteration and break if it's the one I want, then again outside the loop to return the value of mid.

You do not test the "updated mid" at the beginning of each loop. You check the element at the old mid for equality, then update mid. The updating needs to occur at the beginning or end of each loop iteration, not in the middle. Surely you've noticed that you're comparing the same element for equality every time the first two iterations of the loop.

But that's just a little inefficiency in the loop (and the element reported by your equalAlpha function isn't in sync with what's being compared in your greaterAlpha function.)

The real problem is you have the logic for updating the high and low reversed. If the item you're looking for is greater than the element at mid, you set the high to below mid, when you should be looking above mid at that point.

[taymaxi]

Ohhhhh my goodness, I feel stupid. THANK YOU!

The search now works to find most searched-for entries, but not all. Mid doesn't always equal the number of the entry it's searching for. How can I change this?

[taymaxi]

NEVERMIND.

int binarySearch(PhoneEntry &keyP, const vector<PhoneEntry> &entryNames)
{
	int low = 0, 
		high = entryNames.size()-1, 
		mid = (low + high) / 2;

	while (low <= high)
	{	
		if (keyP.equalAlpha(entryNames[mid])) //uses mid before changed
			break;
		mid = (low + high) / 2;
		if (!keyP.greaterAlpha(entryNames[mid]))
			high = mid - 1;
		else if (keyP.greaterAlpha(entryNames[mid]))
			low = mid + 1;
	}

	if (keyP.equalAlpha(entryNames[mid]))
		return mid;
	else
		return (mid * -1);
};

I removed the first equalAlpha test on mid at first (as suggested), but for the function to be able to return any entry, that comparison needs to be there. Otherwise mid might be off by one if (low + high)/2 is a truncated decimal.

At least...I think that's why it needs to be there. Honestly, I'm not totally sure I understand it, but I know that some entries aren't found when it's not there, but all entries can be found when it is.

Thanks for your help!!

[cire]

I removed the first equalAlpha test on mid at first (as suggested)

I never suggested you remove the test. I suggested you update mid at either the beginning of the loop or the end of the loop:

int binarySearch(PhoneEntry &keyP, const vector<PhoneEntry> &entryNames)
{
    int low = 0, 
        high = entryNames.size()-1, 
        mid = (low + high) / 2;

    while (low <= high)
    {	
        if (keyP.equalAlpha(entryNames[mid])) //uses mid before changed
            break;

        if (!keyP.greaterAlpha(entryNames[mid]))
            high = mid - 1;
        else 
            low = mid + 1;

        mid = (low + high) / 2 ;
    }

    if (keyP.equalAlpha(entryNames[mid]))
        return mid;
    else
        return (mid * -1);
};