Unexpected result messing around with own binary search

[alacrite]

#include <iostream>
#include <vector>

using namespace std;

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

int main()
{
vector<int> arrInt;
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<int> list, 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!

 

[Kavya]

#include <iostream>
#include <vector>

using namespace std;

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

int main()
{
vector<int> arrInt;
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<int> list, 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<int> list, 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;
}

 

[Daniel T.]

#include <iostream>
#include <vector>

using namespace std;

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

int main()
{
vector<int> arrInt;
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<int> list, 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

 

[Kai-Uwe Bux]

#include <iostream>
#include <vector>

using namespace std;

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

int main()
{
vector<int> arrInt;
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<int> list, 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<int> arrInt;
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<int> list, 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

 

[Salt_Peter]

#include <iostream>
#include <vector>

using namespace std;

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

int main()
{
vector<int> arrInt;
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<int> list, 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<int> vn;
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
*/