c - 递归二进制搜索函数不会为数组中不存在的值返回 -1

Question

我正在尝试使用递归执行二进制排序函数。它适用于存在于 list[] 结构数组中的值。但是，当我输入一个我知道不在数组内的值时，它不会返回 -1，而是返回垃圾值。我在 MVS 中使用调试器跟踪了代码，但可能(事实上，绝对是)我看不到的东西。

有人能告诉我为什么它不返回 -1 吗？

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

#define MAX 20

typedef struct
{
    char name[MAX] = "";
    char surname[MAX] = "";
    int id;
}patient;

int binarySearch(patient list[], char *target, int top, int bottom, int *comparisons)
{
    int center;
    center = (top + bottom) / 2;
    if (strcmp(list[center].surname, target) == 0)
        return center;
    (*comparisons)++;

    if (top == center || bottom == center)
        return -1;
    if (strcmp(list[center].surname, target) == 1)
        return binarySearch(list, target, center - 1, bottom, comparisons);
    if (strcmp(list[center].surname, target) == -1)
        return binarySearch(list, target, top, center + 1, comparisons);
}

int main(void)
{
    FILE *fi = fopen("patients.txt", "r");

    if (fi == NULL)
        printf("Problem opening file!");
    else
    {
        patient list[MAX];
        int i = 0, comparisons = 0, index;
        char target[MAX] = "";

        while (fscanf(fi, "%s %s %d", &list[i].name, &list[i].surname, &list[i].id) != EOF)
            i++;

        printf("Enter the surname of the patient (END to exit): ");
        scanf("%s", target);

        index = binarySearch(list, target, i, 0, &comparisons);

        printf("%-15s %-15s %-15d\n", list[index].name, list[index].surname, list[index].id);
        printf("%d comparisons\n", comparisons);

    }
}

Answer 1

你得到一个垃圾值，因为你最后的条件是非穷尽的。

当strcmp表示第一个值在第二个值之后时，不需要返回1。唯一的要求是它返回一个正数。小于则和负数 -1 也是如此。因此，您的函数可能会在没有点击 return 的情况下到达终点，这是未定义的行为。

您需要更改 if 链以将返回值与零进行比较。作为一种优化，您应该存储一次比较结果，并在整个条件语句中重复使用它:

int binarySearch(patient list[], char *target, int top, int bottom, int *comparisons)
{
    int center = (top + bottom) / 2;
    (*comparisons)++;
    int cmp = strcmp(list[center].surname, target);
    if (cmp == 0)
        return center;
    if (top == center || bottom == center)
        return -1;
    if (cmp > 0)
        return binarySearch(list, target, center - 1, bottom, comparisons);
    else // cmp < 0 here
        return binarySearch(list, target, top, center + 1, comparisons);
}

另请注意，为了以准确的方式计算比较次数，(*comparisons)++ 应该发生在 strcmp 调用之前。