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++ - 在用户插入数据之前创建结构对象时,Vector 返回乱码

c - 当字符指针指向字符串时,如何分配内存?

c - 小型嵌入式系统的好的脚本语言是什么?

c - 编写代码以查找字符串 C 中的第一个整数

c - 关于在 C 中使用递归

python - 如何并行洗牌大量项目,python

c++ - 指向错误 : Linking Error in C++ 的指针

c - 如何在 printf 中表示变量类型 unsigned long

algorithm - STM32L1xx 上的闪存 ECC 算法

javascript - 为什么DOM树是oder preorder,深度优先遍历?