对于数组中不存在的值，递归二进制搜索函数不返回-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，这是未定义的行为。

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

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调用之前发生。

Answer 2

如何节省时间：1）确保完全启用编译器警告。 2）使用一个好的编译器。

我希望下面的内容生成一个警告，例如“警告：控制到达非空函数的结束”，为您提供比堆栈溢出更好更快的反馈。

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

---

其他好的编译器反馈"error: expected ':', ',', ';', '}' or '__attribute__' before '='"

typedef struct {
  char name[MAX] = "";  // not valid to initialize.

“在MVS中使用调试器跟踪代码” - >让我想知道你是否正在将C代码编译为C ++代码。