我正在寻找排序数组中的元素 x。它比较 xx 或数组范围等于零 我在出错的地方遇到段错误 我找不到我的代码在下面 我正在 gcc 编译器中编译。
#include <iostream>
using namespace std;
// iterative
int bsearch(int a[], int sz, int x)
{
int low = 0;
int high = sz -1;
while(low <= high) {
int mid = (low+high)/2;
if(x < a[mid])
high = mid - 1;
else if(x > a[mid])
low = mid + 1;
else
return a[mid];
}
return -1;
}
// recursive
int bsearch_recursive(int a[], int low, int high, int x)
{
if(low > high) return -1;
int mid = (low + high)/2;
if(x < a[mid])
bsearch_recursive(a, low, mid-1, x);
else if(x > a[mid])
bsearch_recursive(a, mid+1, high, x);
else
return a[mid];
}
void print(int n)
{
if(n == -1) {
cout << "not found" << endl;
return;
}
cout << "found" << endl;
}
int main()
{
int a[]={3, 7, 9, 16, 23, 34, 67, 87, 92};
int arraySize = sizeof(a)/sizeof(int);
int result;
result = bsearch(a, arraySize, 7);
print(result);
result = bsearch(a, arraySize, 92);
print(result);
result = bsearch(a, arraySize, 77);
print(result);
result = bsearch_recursive(a, 0, arraySize-1, 7);
print(result);
result = bsearch_recursive(a, 0, arraySize-1, 92);
print(result);
result = bsearch_recursive(a, 0, arraySize-1, 77);
print(result);
return 0;
}
最佳答案
您的递归搜索需要每个路径都有返回值,否则其结果是不确定的。
递归函数的工作方式与其他函数完全一样——如果它声称要返回一个值,它就必须这样做。它不仅会自动返回终止递归调用的结果。
int bsearch_recursive(int a[], int low, int high, int x)
{
if(low > high) return -1;
int mid = (low + high)/2;
if(x < a[mid])
return bsearch_recursive(a, low, mid-1, x);
else if(x > a[mid])
return bsearch_recursive(a, mid+1, high, x);
else
return a[mid];
}
你的编译器应该警告过你——如果没有,打开更多警告。
如果确实如此,而您不在乎,请开始听取警告。
关于c++ - 使用迭代和递归的二进制搜索算法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/24011645/