Как вернуть NULL, если искомый двоичный номер отсутствует в индексе?

Question

Я пишу код, который по существу закончен с одной серьезной проблемой.Я написал двоичную функцию поиска, возвращающую найденный индекс.Всякий раз, когда я запускаю свой код и ищу любую степень 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;
}

Я хочу, чтобы оператор else в функции main () выполнялся всякий раз, когда искомое значение отсутствует в индексе.

Answer 1

Ваша проблема в том, что для рекурсии нет базового варианта

Подумайте об этом так: ваша стрелка всегда будет больше или меньше середины, если число не находится в массиве

Это означает, что он никогда не достигнет последнего, всегда будет происходить рекурсивное увеличение или уменьшение, пока не будет предпринята попытка разыменования тарабарщины, отсюда ошибка сегментации

Вам нужно добавить старый хороший базовый вариант в ваш двоичный файлискать так:

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);
    }   
}