struggling with the logic of something - code inside C++

This topic is 2929 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

Recommended Posts

Hi guys just a very quick question. I am writing a function to do a binary search and I have it working only because i stuck a +1 on the end of the return value. Can someone explain to me in simple english why I am adding a +1 when i return the vaule of the position in the array? I have marked it the return clearly in the code that I am referring to.

int bSearch(int myArray[],int totalElements, int key)
{
int first = 0;
int last = totalElements;
int mid;

while (first <= last)
{
mid = (first + last) / 2;

if (key > myArray[mid]) // search top half
first = mid + 1;
else if (key < myArray[mid]) // search bottom half.
last = mid - 1;
else //it is the position
return mid + 1;    ////////////<<<<<<<<THIS BIT WITH + 1??
}


Thanks for any help guys. Kind Regards David [Edited by - bentaberry on February 9, 2010 4:08:47 PM]

Share on other sites
What is data'? EDIT: Other than that, and that we don't know what you are returning when you don't find the element, your code seems fine to me, if you remove the + 1'.

Share on other sites
Quote:
 Original post by alvaroWhat is data'? EDIT: Other than that, and that we don't know what you are returning when you don't find the element, your code seems fine to me, if you remove the + 1'.

Edited that array name, messed about with it in the text editor here and missed that name change sorry.

Its the +1 i have a problem with, without it my program is wrong. for example i put in the number 45 for it to find the position of and it returns the array element number just before hence me adding the +1 but I just cant see why I had to do that.

dont worry about the return code for when it doesnt find anything, thats just in there as a placehold for another bit of code im writing.

anyone else see why im having to do the +1 to get correct results in the program?

Kind Regards
David

Share on other sites
should it be

while (first < last)

while (first <= last)

??

if last is the totalElements in your array, and first is starting at 0, it should just be <. I don't know if that helps though, just something i noticed.

Share on other sites
Oh, I think supamike's observation is correct. As it is, in certain cases (e.g. if you call it with an empty range), your code would access the element that is one-past the end.

Bentaberry, could you post a complete little program that shows the problem with the +1'? You are probably getting confused with the way indices work in C and C++.

By the way, is Bentaberry a Basque name?

Share on other sites
Quote:
 Original post by alvaroOh, I think supamike's observation is correct. As it is, in certain cases (e.g. if you call it with an empty range), your code would access the element that is one-past the end.Bentaberry, could you post a complete little program that shows the problem with the +1'? You are probably getting confused with the way indices work in C and C++.By the way, is Bentaberry a Basque name?

I will put the complete program up later if i cant figure it out by staring at it for a while.

How on earth did you know that was a Basque name?

Kind Regards
David

Share on other sites
shouldn't last = total elements - 1?

Share on other sites
The +1 doesn't totally fix the problem. It happened to compensate for off by one problems in the rest of the code when searching for that particular item, but it would almsot certainly make it wrong for some other items.
The current code is wrong with or without it.

You might like to read the article I wrote on searching some time ago.

Share on other sites
Quote:
 Original post by iMalcThe +1 doesn't totally fix the problem. It happened to compensate for off by one problems in the rest of the code when searching for that particular item, but it would almsot certainly make it wrong for some other items.The current code is wrong with or without it.You might like to read the article I wrote on searching some time ago.

Kind Regards
David