二元搜索使用递归

我不明白为什么这不会返回键，它似乎跳过了一步，我觉得逻辑是直的，如果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; 
}

来源

2013-04-22 user2206227

@Paulpro：[C++版本]（http://www.cplusplus.com/reference/algorithm/binary_search/）会更好;它是类型安全的并且可能更快。 – 2013-04-22 18:24:14

真棒谢谢大家！ – user2206227 2013-04-22 18:31:44

您忘记了return声明。您应该返回递归调用的结果：

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

应该

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

否则您最初的通话将执行体的其余部分，最后总是回到-1，除非你找到之前的关键第一次递归。

通过添加return语句，可以中断递归调用的控制流（即，您不会返回“not found”值），并且您将最后一次返回值传播到调用堆栈中，直到第一次调用，最后返回你想要的值。

来源

2013-04-22 18:11:45 Thibaut

它一切正常，但你不会返回正确的值。在else-if语句中，您将调用函数递归，但返回的值不会传递给初始调用！尝试：

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

和

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

这应该工作。

- 编辑：嗯，我想我已经放缓;）

来源

2013-04-22 18:20:53 CyDek

你也应该补充：

if(endptr == midptr) return -1;

计算endptr避免无限循环柜面不阵列，例如搜索部件后21 ..等

来源

2013-04-22 18:20:57

二元搜索使用递归

回答

相关问题