使用递归的二进制搜索

Question

我无法弄清楚为什么这不会返回键,它似乎是跳过步骤,我觉得逻辑是直的,如果midptr小于键然后搜索右边的其他搜索左侧.但它没有返回键,它返回-1.救命？这是代码和功能

#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;
}

Answer 1

你忘了这些return陈述.您应该返回递归调用的结果:

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

应该

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

否则,您的初始调用将执行正文的其余部分并始终返回-1,除非您在第一次递归之前找到该键.

通过添加return语句,您可以打破递归调用的控制流(即,您不返回"未找到"值),并且您将在调用堆栈中一直传播最后一个返回值,直到第一个调用,最后返回你想要的值.