我正在写一段代码,基本上解决了一个主要问题。我写了一个二进制搜索函数,返回找到的索引。每当我运行我的代码并搜索 2 的任何幂时,它都能正常工作。但是,每当我输入任何其他数字(例如 50)时,它都会返回错误。
在我的代码末尾,我有一个 else 语句说如果没有其他语句返回一个值返回 NULL,所以我遇到了一些麻烦。谢谢。我在 Xcode 和 UNIX 服务器上运行,但我注释掉了在 UNIX 服务器上运行的行。
#include <stdio.h>
#include <stdlib.h>
int* search(int* begin, int* end, int needle);
int main(int argc, char **argv) { //int argc = 1, char **argv array of char pointers
int num = 0;
int nums[10], i;
int *found = NULL;
if(argc != 2) {
printf("Enter a number to a power of 2 to search for:\n");
scanf("%d" , &num);
}
// num = atoi(argv[1]);
for(i = 0; i < 10; i++) { // initialzes array by shifting binary code to the left adding powers of 2
nums[i] = 1 << i; }
found = search(nums, &nums[9], num);
if(found) {
printf("Number %d found in index %ld.\n", num, found - nums);
}
else {
printf("Number %d was not found.\n", num);
}
return 0;
}
int* search(int* begin, int* end, int needle){
int *middle = (end-begin)/2 + begin;
if(*middle == needle){
return middle;
}
else if(needle < *middle){
end = middle;
return search(begin, end-1, needle);
}
else if(needle > *middle)
{
begin = middle;
return search(begin+1, end, needle);
}
else
return NULL;
}
我希望 main() 函数中的 else 语句在搜索的值不在索引中时执行。
最佳答案
你的问题是你的递归没有基本情况
这样想:如果数字不在数组中,你的针总是比中间大或小
这意味着它永远不会到达最后一个 else,它总是会递归递增或递减,直到它尝试取消引用乱码,因此出现段错误
您需要像这样将旧的良好基本情况添加到您的二进制搜索中:
int* search(int* begin, int* end, int needle) {
int *middle = (end-begin)/2 + begin;
if(begin == end) {
//recursion ends when there are no more segments to divide in two
//so after your final single element segment, a decrement or increment will happen
//making your end and begin pointers the same
return NULL;
}
else if(*middle == needle) {
return middle;
}
else if(needle < *middle) {
end = middle;
return search(begin, end-1, needle);
}
else if(needle > *middle) {
begin = middle;
return search(begin+1, end, needle);
}
}
关于c - 如果二进制搜索数字不在索引中,如何返回 NULL?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/54453023/