By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
457,949 Members | 1,511 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 457,949 IT Pros & Developers. It's quick & easy.

Unexpected result messing around with own binary search

P: n/a
#include <iostream>
#include <vector>

using namespace std;

int binarySearch(vector<int>, int, int, int);

int main()
{
vector<intarrInt;
for(int i=0; i<1000; i++)
{
arrInt.push_back(i);
}
int pos = 0;
if(pos=binarySearch(arrInt, 12, 0, 999))
cout<<"pos "<<pos<<endl;
//cout<<arrInt[pos];
else
cout<<"Not Found"<<endl;

return 0;

}
int binarySearch(vector<intlist, int value, int left, int right)
{
int mid = (left+right)/2;
if(value>list[mid])
binarySearch(list, value, mid, right);
else if (value<list[mid])
binarySearch(list, value, left, mid);
else if(value==list[mid])
{
cout<<"about to return "<<mid<<endl;
return mid;
}
else
return -1;
}

When this runs the output I get it:
about to return 12
pos 1244568

expected output:
about to return 12
pos 12

Anyone know why the return value from binarySearch is wrong?

thanks!

Oct 29 '06 #1
Share this Question
Share on Google+
4 Replies


P: n/a
al******@gmail.com wrote:
#include <iostream>
#include <vector>

using namespace std;

int binarySearch(vector<int>, int, int, int);

int main()
{
vector<intarrInt;
for(int i=0; i<1000; i++)
{
arrInt.push_back(i);
}
int pos = 0;
if(pos=binarySearch(arrInt, 12, 0, 999))
cout<<"pos "<<pos<<endl;
//cout<<arrInt[pos];
else
cout<<"Not Found"<<endl;

return 0;

}
int binarySearch(vector<intlist, int value, int left, int right)
{
int mid = (left+right)/2;
if(value>list[mid])
binarySearch(list, value, mid, right);
else if (value<list[mid])
binarySearch(list, value, left, mid);
else if(value==list[mid])
{
cout<<"about to return "<<mid<<endl;
return mid;
}
else
return -1;
}

When this runs the output I get it:
about to return 12
pos 1244568

expected output:
about to return 12
pos 12

Anyone know why the return value from binarySearch is wrong?
I don't know what is the problem with your code but can't you just use
this non-recursive version.

int binarySearch(vector<intlist, int value, int left, int right)
{
int mid =(left+right)/2;
while((left<=right)&&(list[mid]!=value))
{
if(value<list[mid])
right=mid-1;
else
left=mid+1;

mid=(left+right)/2;
}

if(value==list[mid])
{
cout<<"about to return "<<mid<<endl;
return mid;
}
else
return -1;
}

Oct 29 '06 #2

P: n/a
al******@gmail.com wrote:
#include <iostream>
#include <vector>

using namespace std;

int binarySearch(vector<int>, int, int, int);

int main()
{
vector<intarrInt;
for(int i=0; i<1000; i++)
{
arrInt.push_back(i);
}
int pos = 0;
if(pos=binarySearch(arrInt, 12, 0, 999))
cout<<"pos "<<pos<<endl;
//cout<<arrInt[pos];
else
cout<<"Not Found"<<endl;

return 0;

}
int binarySearch(vector<intlist, int value, int left, int right)
{
int mid = (left+right)/2;
if(value>list[mid])
binarySearch(list, value, mid, right);
else if (value<list[mid])
binarySearch(list, value, left, mid);
else if(value==list[mid])
{
cout<<"about to return "<<mid<<endl;
return mid;
}
else
return -1;
When I compiled your code I got the following:

warning: control reaches end of non-void function.

Follow the logic in the above function. if value list[mid] then call
binarySearch, and then what? What should it return?
}
In general, you would be better off making a non-recursive function. If
allowed, you should use the binary search functions provided by the
standard.
http://www.sgi.com/tech/stl/binary_search.html
http://www.sgi.com/tech/stl/lower_bound.html

--
To send me email, put "sheltie" in the subject.
Oct 29 '06 #3

P: n/a
al******@gmail.com wrote:
#include <iostream>
#include <vector>

using namespace std;

int binarySearch(vector<int>, int, int, int);

int main()
{
vector<intarrInt;
for(int i=0; i<1000; i++)
{
arrInt.push_back(i);
}
int pos = 0;
if(pos=binarySearch(arrInt, 12, 0, 999))
cout<<"pos "<<pos<<endl;
//cout<<arrInt[pos];
else
cout<<"Not Found"<<endl;

return 0;

}
int binarySearch(vector<intlist, int value, int left, int right)
{
int mid = (left+right)/2;
if(value>list[mid])
binarySearch(list, value, mid, right);
you are not returning:

return ( binarySearch(list, value, mid, right) );
else if (value<list[mid])
binarySearch(list, value, left, mid);
again:

return ( binarySearch(list, value, left, mid) );
else if(value==list[mid])
{
cout<<"about to return "<<mid<<endl;
return mid;
}
else
return -1;
}

When this runs the output I get it:
about to return 12
pos 1244568

expected output:
about to return 12
pos 12

Anyone know why the return value from binarySearch is wrong?
BTW: The design is questionable. The return of -1 to indicate failure got
you confused already. std::binary_search is a much better design. Just use
it.

Also: there is yet two more bugs.

a) the test:

if( pos = binarySearch(arrInt, 12, 0, 999) )

does not what you apparently think it does. Probably, you want

int pos = binarySearch(arrInt, 1, 5, 8);
if ( pos >= 0 )
However if you try to see why by doing

if( pos = binarySearch(arrInt, 1200, 0, 999) )

you discover the second issue:

b) The code might recurse indefinitely finally segfaulting due to stack
limitations. One can even do this when the search should find an entry:

#include <iostream>
#include <vector>

using namespace std;

int binarySearch(vector<int>, int, int, int);

int main()
{
vector<intarrInt;
for(int i=0; i<1000; i++)
{
arrInt.push_back(i);
}
int pos = binarySearch(arrInt, 1, 5, 8);
if ( pos >= 0 )
cout<<"pos "<<pos<<endl;
//cout<<arrInt[pos];
else
cout<<"Not Found"<<endl;
return 0;
}
int binarySearch(vector<intlist, int value, int left, int right)
{
int mid = (left+right)/2;
if(value>list[mid])
return ( binarySearch(list, value, mid, right) );
else if (value<list[mid])
return ( binarySearch(list, value, left, mid) );
else if(value==list[mid])
{
cout<<"about to return "<<mid<<endl;
return mid;
}
else
return -1;
}

Some branch of the recursion, under some circumstances is not making
progress. I leave the fix as an exercise.
Best

Kai-Uwe Bux
Oct 29 '06 #4

P: n/a
al******@gmail.com wrote:
#include <iostream>
#include <vector>

using namespace std;

int binarySearch(vector<int>, int, int, int);

int main()
{
vector<intarrInt;
for(int i=0; i<1000; i++)
{
arrInt.push_back(i);
}
int pos = 0;
if(pos=binarySearch(arrInt, 12, 0, 999))
cout<<"pos "<<pos<<endl;
//cout<<arrInt[pos];
else
cout<<"Not Found"<<endl;
Main does not call recursive functions recursively. It can't. Only a
recursive function can call itself.
So you don't need an if condition or for that matter, any conditional
statements.
Main does not care or know that the function is recursive.

int pos = binarySearch(vn, 12, 0, vn.size() - 1);
std::cout << "pos "<< pos << std::endl;
>
return 0;

}
int binarySearch(vector<intlist, int value, int left, int right)
{
int mid = (left+right)/2;
Your function creates a local copy of the vector everytime the
binarySearch function is called.
why not pass the vector by reference?
if(value>list[mid])
binarySearch(list, value, mid, right);
Are you not attempting to call this function recursively? Don't you see
the compiler's warning about reaching the end of a function that is
expected to return an integer?

if(value list[mid]) {
return binarySearch(list, value, mid, right);
}
else if (value<list[mid])
binarySearch(list, value, left, mid);
missing return again...

Now, if value is neither greater nor less, its obviously equal

else // equal
{
cout<<"about to return "<<mid<<endl;
return mid;
}
else if(value==list[mid])
{
cout<<"about to return "<<mid<<endl;
return mid;
}
else
return -1;
}

When this runs the output I get it:
about to return 12
pos 1244568

expected output:
about to return 12
pos 12

Anyone know why the return value from binarySearch is wrong?
You'ld be surprised, the pos you see is not the pos you think. the
compiler has no choice but to create a local copy of the variable in
the if loop. And since your function was not returning, the remnants of
a local are seen in the ouput. Remember that everytime you call a
function recursively, a new stack is created (you'll see that if you
set a breakpoint in the function below). So in essense, a recursive
call which is expected to return (but does not) leaves a function stack
hanging in mid air. Thats one of the reasons these are rare in C++.

set a breakpoint in binarySearch and observe.

#include <iostream>
#include <vector>

int binarySearch(std::vector<int>& list, int value, int left, int
right)
{
int mid = (left + right)/2;
std::cout << "mid "<< mid << std::endl;
if(value list[mid]) {
return binarySearch(list, value, mid, right);
}
else if (value < list[mid]) {
return binarySearch(list, value, left, mid);
}
else { // must be equal
std::cout << "about to return " << mid << std::endl;
return mid;
}
}

int main()
{
std::vector<intvn;
for(int i=0; i<1000; i++)
{
vn.push_back(i);
}
int pos = binarySearch(vn, 12, 0, vn.size() - 1);
std::cout << "pos "<< pos << std::endl;
return 0;
}

/*
mid 499
mid 249
mid 124
mid 62
mid 31
mid 15
mid 7
mid 11
mid 13
mid 12
about to return 12
pos 12
*/

Oct 29 '06 #5

This discussion thread is closed

Replies have been disabled for this discussion.