Блог

У меня проблема с возвращаемым значением в двоичном поиске, который я написал.

У меня есть следующее:

int BinarySearch(char *instructions[], int low, int high, char *string);

 int main() {
    char *instructions[];  // some array of strings - it does not include the string "jk"
    char *string = "jk";
    int high = inst_len;
    int x = binarySearch(instructions, 0, high, string);
    if (x == -1)
        printf("not found");
    else if (x == -2)
    printf("error");
    else
    printf("Found at %d", x);
}

int binarySearch(char *instructions[], int low, int high, char *string) {

    int mid = low   (high - low) / 2;

    // Not found
    if (high <= low)
        return -1;

    // If instructions[mid] is less than string
    else if (strcmp(instructions[mid], string) > 0)
        binarySearch(instructions, low, mid-1, string);

    // If instructions[mid] is larger than string
    else if (strcmp(instructions[mid], string) < 0)
        binarySearch(instructions, mid 1, high, string);

    // Return position
    else
        return mid;
}
  

Независимо от того, что, в main , BinarySearch всегда возвращает 0 . Однако, когда я помещаю операторы печати в алгоритм двоичного поиска, я получаю -1 возврат. Почему это происходит?? Это очень странно!

Вы хотите, чтобы это:

 // If instructions[mid] is less than string
else if (strcmp(instructions[mid], string) > 0)
    return binarySearch(instructions, low, mid-1, string);

// If instructions[mid] is larger than string
else if (strcmp(instructions[mid], string) < 0)
    return binarySearch(instructions, mid 1, high, string);
  

Обратите return внимание на часть «».

Вы также выполняете сравнение больше раз, чем нужно; вы можете сохранить результат strcmp , чтобы сделать это только один раз:

 int r = strcmp(instructions[mid], string);

if (r > 0)
    return binarySearch(instructions, low, mid-1, string);
else if (r < 0)
    return binarySearch(instructions, mid 1, high, string);