CODEWITHSUNDEEP
crecursionbinary-search
SarpSTA
SarpSTA

Reputation: 279

Recursive binary searching function doesn't return -1 for value that's not existant in the array

I'm trying to do a binary sorting function using recursion. It works well with the values that exist in the list[] structure array. However, when I punch in a value that I know is not inside the array, instead of returning -1, it returns garbage value. I traced the code using debugger in MVS but there might be (in fact, definitely is) something that I just can't see.

Can somebody tell me why it doesn't return -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);

    }
}

Upvotes: 1

Views: 100

Answers (2)

chux
chux

Reputation: 153468

How to save time: 1) ensure compiler warnings are fully enabled. 2) Use a good compiler.

I'd expect the below to to generate a warning like " warning: control reaches end of non-void function", providing you good and faster feedback than stack-overflow.

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

Other good compiler feedback "error: expected ':', ',', ';', '}' or '__attribute__' before '='"

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

"traced the code using debugger in MVS" --> leads me to wonder if you are compiling your C code as C++ code.

Upvotes: 1

Sergey Kalinichenko
Sergey Kalinichenko

Reputation: 726579

You get a garbage value because your conditionals at the end are non-exhaustive.

When strcmp indicates that the first value is after the second value, is not required to return 1. The only requirement is that it returns a positive number. Same goes for less then and negative one -1. Therefore, your function may end up reaching the end without hitting return, which is undefined behavior.

You need to change your chain of ifs to compare return values with zero. As an optimization, you should store comparison result once, and reuse it throughout your conditionals:

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

Also note that in order to account for the number of comparisons in an accurate way, (*comparisons)++ should happen before strcmp call.

Upvotes: 4

Related Questions