c - 如果二进制搜索的数字不在索引中,如何返回 NULL?
问题描述
我正在编写一个代码,它基本上完成了一个主要问题。我写了一个二分搜索函数,返回找到的索引。每当我运行我的代码并搜索 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);
}
}
推荐阅读
- r - r - 按年份或星期几计算间隔小时数
- jmeter - JMeter HTTP 原始请求错误 400 错误请求
- java - Google Play 控制台警告应用正在使用不受支持的 API
- java - 你如何传递一个列表
如果 Placeholder 已经是一个接口,则到一个包 - python - 使用python从HTML表格的行中提取文本
- sql - 根据 groupBy 的结果选择 pyspark 数据帧行
- sql - 具有多个条件的 SQL 查询 2020 年 3 月 18 日
- linux - EC2 不向 Cloudwatch 发送日志
- python - 将不同表中的多条记录组合成一个字符串
- java - Java:如何解决错误:“隐式超级构造函数未定义”