因此,我正在尝试为我的 C++ 类创建一个二进制排序算法,但是当我的 binarySearch 函数运行时,我一直遇到段错误。无论我和我的室友怎么看,我们都找不到问题所在。任何帮助将不胜感激。
int binarySearch(int arr[], int k, int first, int last)
{
if(arr[first] <= arr[last])
{
int mid = (first + last) / 2;
if(k == arr[mid])
{
return mid;
}
else if (k < arr[mid])
{
return binarySearch(arr, k, first, mid-1);
}
else return binarySearch(arr, k, mid+1, last);
}
else if(arr[first] >= arr[last])
{
int mid = (first + last) / 2;
if(k == arr[mid])
{
return mid;
}
else if (k < arr[mid])
{
return binarySearch(arr, k, mid+1, last);
}
else return binarySearch(arr, k, first, mid-1);
}
else return -1;
}
修复段错误后,我注意到我的逻辑中一定有错误,因为程序一直输出无法找到键,即使它存在于数组中。
最佳答案
如果您要搜索的元素在数组中,您的代码实际上可以工作。但是,它不会捕获不正确的输入。
调用函数时,请确保:
-
first
和last
介于 0 和(数组长度 - 1)之间 -
first < last
例如:如果数组有 10 个元素,则 first 和 last 必须介于 0 和 9 之间。
尝试 this :
int main() {
int a[] = {134, 232, 233, 234, 587, 623, 793, 802, 963, 1074};
int b[] = {10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
int na = binarySearch(a, 587, 0, 9);
int nb = binarySearch(b, 3, 0, 9);
printf("na: %d\n", na); // prints 'na: 4'
printf("nb: %d\n", nb); // prints 'nb: 7'
}
如果您要搜索的元素不在数组中,
那么递归永远不会终止,
您可以通过将以下内容添加到 binarySearch()
的头部来解决这个问题:
if (first == last && k != arr[first])
return -1;
关于c++ - C++ 中的二进制搜索 : Ascending + Descending Ordered Arrays,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/33009726/