c++ - 使用递归的二进制搜索

Question

我不明白为什么这不会返回 key ，它似乎跳过了这一步，我觉得逻辑是直截了当的，如果 midptr 小于 key 则搜索右侧，否则搜索左侧。但它没有返回键，它返回 -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 结束，除非您在第一次递归之前找到 key 。

通过添加 return 语句，您打破了递归调用的控制流(即您不返回“未找到”值)，并且您将在调用堆栈中向上传播最后一个返回值，直到第一次调用，最后返回你想要的值。