c - 如果二进制搜索数字不在索引中,如何返回 NULL?

标签 c algorithm pointers search binary

我正在写一段代码,基本上解决了一个主要问题。我写了一个二进制搜索函数,返回找到的索引。每当我运行我的代码并搜索 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/

相关文章:

c++ - Openssl aes.h [链接器错误] undefined reference

用于阅读 doc、docx、pdf 的 C 程序

c - UTF-8 到 Unicode 转换

python - 围绕正方形滚动一个圆圈

c++ - 获取笛卡尔积的算法

c++ - 通过来自另一个类的指针访问时包含 "random"值的类的数组属性

c - 为什么在下面的函数中递增数组 "a"不是错误?

c - 如何随机打乱 C 中的链表

algorithm - 多循环的时间复杂度

C 未正确读取输入值