binary search using recursion

Question

I can not figure out why this will not return the key, it seems to be skipping over the step, the logic i feel is straight, if midptr is less than key then search right else search left side. but its not returning key it returns -1. help? here is the code and function

#include<iostream>
using namespace std;


int binsrch(int *raw, unsigned int size, int key);




int main()
{
  int raw[] = {1,3,5,7,11,23, 48};
  cout << binsrch(raw, 7, 11) << endl;


  system("pause");
  return 0;
}



int binsrch(int *raw, unsigned int size, int key)
{
    int *begptr, *endptr ,*midptr;
//see if we already have the key

if(*raw == key)
  return key;

begptr = raw;
endptr = raw + (size - 1);
midptr = raw + (size / 2);

cout << "#" <<*midptr << " size:" << size<<  endl;
if(*midptr == key)
{
  return key;
}
else  if( *midptr < key) //Search Right
{
  cout << "#" <<*(midptr+1) << " size:" << size<<  endl;
  binsrch(midptr + 1, size / 2, key);
}
else if(*midptr > key) //Search Left
{
    cout << " #" <<*midptr << " size:" << size<<  endl;
    binsrch(begptr, size / 2, key);
}

return -1;
}

@Paulpro: The C++ version would be better; it's type-safe and potentially faster. — Mike Seymour
– Mike Seymour, Commented Apr 22, 2013 at 18:24

Thibaut · Accepted Answer · 2013-04-22 18:17:47Z

5

You forgot the return statements. You should return the result of the recursive calls:

binsrch(midptr + 1, size / 2, key);

should be

return binsrch(midptr + 1, size / 2, key);

Otherwise your initial call will execute the rest of the body and always end up returning -1, unless you find the key before the first recursion.

By adding the return statement, you break the control flow of the recursive call (ie you don't return the "not found" value), and you will propagate the last return value all the way up in the call stack, until the first call, and finally return the value you want.

edited Apr 22, 2013 at 18:17

answered Apr 22, 2013 at 18:11

Thibaut

2,4601 gold badge17 silver badges28 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

CyDek · Accepted Answer · 2013-04-22 18:20:53Z

0

It all works fine, but you don't return the correct value. In the else-if-statements you call the function recursive, but the returned values are not passed through to the initial call! Try:

return binsrch(midptr + 1, size / 2, key);

and

return binsrch(begptr, size / 2, key);

That should work.

-Edit: Well I guess I've been to slow ;)

answered Apr 22, 2013 at 18:20

CyDek

1587 bronze badges

Comments

nishant pathak · Accepted Answer · 2013-04-22 18:20:57Z

0

you should also add :

if(endptr == midptr) return -1;

after calculating endptr to avoid infinite loop incase of searching element not in array such as 21.. etc

answered Apr 22, 2013 at 18:20

nishant pathak

3691 gold badge4 silver badges17 bronze badges

Collectives™ on Stack Overflow

binary search using recursion

3 Answers 3

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related