为什么我在这个二分搜索实现中遇到分段错误？

Question

我目前正在尝试通过递归实现二进制搜索并为用户输入创建提示。每当我输入一个数字并搜索它时，我总是会遇到分段错误（核心已转储）。我在 CS50 设备中编写了这段代码。

#include <stdio.h>
#include <stdlib.h>
#include <cs50.h>
#include <ctype.h>
#include <string.h>


int findMidpoint(int min, int max);
int binarySearch(int key, int array[], int min, int max);


int main(int argc, string argv[])
{
    int array[] = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23};
    printf("Please search for a number : ");
    int key = GetInt();
    int search = binarySearch(key, &array, array[0], array[22]);
    printf("Result: %i \n", search);
}

int findMidpoint(int min, int max)
{
    int sum = min + max;
    int mid = sum/2;

    return mid;
}

int binarySearch(int key, int array[], int min, int max)
{
    if(min > max)
    {
        return -1;
    }
    else
    {
        int midpoint = findMidpoint(min, max);

        if(array[midpoint] < key)
        {
            binarySearch(key, array, midpoint+1, max);
        }

        else if(array[midpoint] > key)
        {
            binarySearch(key, array, midpoint-1, max);
        }
        else
        {
            return midpoint;
        }

    }

    return -1;
}

Answer 1

min 和 max 值是第一个和最后一个元素的索引，而不是值。因此，您应该使用索引调用该函数：

search = binarySearch(key, array, 0, 22);

注意 array 之前没有符号 &：数组将被自动视为指向其第一个元素的指针。（这里 &array 不是正确的类型；您应该得到警告。）

当你递归时，你把数组分成两半，如果中点不是你想要的值，就在左边和右边的一半。你答对了右半部分：

binarySearch(key, array, midpoint+1, max);

但对于左边部分，mitpoint - 1是上限：

binarySearch(key, array, min, midpoint - 1);

编辑：其他答案显示，但我错过了：当然，您必须return递归调用[=19=的结果].

Answer 2

这是经过一些修改后可以正常工作的代码：

#include <stdio.h>
#include <stdlib.h>
#include <cs50.h>
#include <ctype.h>
#include <string.h>

int findMidpoint(int min, int max);
int binarySearch(int key, int array[], int min, int max);

int main(int argc, char** argv) {
    int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17,
            18, 19, 20, 21, 22, 23 };
    printf("Please search for a number : ");
    int key = GetInt();
    int search = binarySearch(key, array, 0, 22);
    printf("Result: %i \n", search);
}

int findMidpoint(int min, int max) {
    int sum = min + max;
    int mid = sum / 2;

    return mid;
}

int binarySearch(int key, int array[], int min, int max) {
    int midpoint = findMidpoint(min, max);
    if (array[midpoint] < key) {
        return binarySearch(key, array, midpoint + 1, max);
    } else if (array[midpoint] > key) {
        return binarySearch(key, array, min, midpoint - 1);
    } else {
        return array[midpoint];
    }
    return -1;
}

请注意，每次递归调用它时，您都需要 return binarySearch 的结果。

Answer 3

应用程序实际上因堆栈溢出而崩溃，因为算法没有正确实现。

按照维基百科上的算法描述：http://en.wikipedia.org/wiki/Binary_search_algorithm

添加了一些 returns，修改了递归调用（GetInt 替换为硬编码值）：

#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <string.h>

int findMidpoint(int min, int max);
int binarySearch(int key, int array[], int min, int max);


int main(int argc, char** argv)
{
    int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23 };
    printf("Please search for a number : ");
    int key = 10;
    int search = binarySearch(key, (int*)(&array), 0, 22);
    printf("Result: %i \n", search);
    getchar();
}

int findMidpoint(int min, int max)
{
    int sum = min + max;
    int mid = sum / 2;

    return mid;
}

int binarySearch(int key, int array[], int min, int max)
{
    if (min > max)
        return -1;
    else
    {
        int midpoint = findMidpoint(min, max);

        if (array[midpoint] < key)
            return binarySearch(key, array, midpoint + 1, max);
        else if (array[midpoint] > key)
            return binarySearch(key, array, min, midpoint - 1);
        else
            return midpoint;
    }

    return -1;
}

为什么我在这个二分搜索实现中遇到分段错误？

Why am I getting an Segmentation fault in this implementation of binary search?

c

cs50