Sign in to follow this  
bentaberry

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

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 this post


Link to post
Share on other sites
Quote:
Original post by alvaro
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'.



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 this post


Link to post
Share on other sites
should it be

while (first < last)

instead of

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 this post


Link to post
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 this post


Link to post
Share on other sites
Quote:
Original post by alvaro
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?


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 this post


Link to post
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 this post


Link to post
Share on other sites
Quote:
Original post by iMalc
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.


Thanks for the link.

Kind Regards
David

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this