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??
}
struggling with the logic of something - code inside C++
Author
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.
Thanks for any help guys.
Kind Regards
David
[Edited by - bentaberry on February 9, 2010 4:08:47 PM]
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'.
Author
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
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.
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.
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?
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?
Author
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
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.
The current code is wrong with or without it.
You might like to read the article I wrote on searching some time ago.
Author
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
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
