c - 二分查找递归的问题

Question

我是初级 C 语言和算法。

我尝试使用递归进行二进制搜索，但我不明白如何检查数组中是否不存在数字。

这是我的代码:

#include <stdio.h>

#define SIZE 15
#define midpoint(start, end) (start + end) / 2

void fill_array(int array[]);

int find(int target, int array[], int start, int end);

int main() {
    int array[SIZE];

    fill_array(array);
    return find(2, array, 0, SIZE);
}

void fill_array(int array[]) { //here I just fill array 
    for (int i = 0, number = 0; i <= SIZE; ++i) {
        array[i] = number++;
        number++;
    }
}

int find(int target, int array[], int start, int end) {
    int mid;
    mid = midpoint(start, end);

    if (target > array[mid]) {  
        find(target, array, mid + 1, end);
    }

    if (target < array[mid]) {
        find(target, array, start, mid - 1);
    }

    if (target == array[mid]) {
        printf("%d\n", mid);
    }
}

如果数组中不存在数字，我想返回 (-1)。

Answer 1

您的代码中存在多个问题:

• 将 midpoint() 定义为宏很容易出错。您的定义没有正确括起来，它应该是:

  #define midpoint(start, end) (((start) + (end)) / 2)
  

  写成总和的一半，它实际上会为 start 和 end 的大值调用未定义的行为，一个更安全的版本是 start + (end - start)/2，但不应在宏中使用，因为它会对 start 求值两次。直接把代码写在函数里面就可以了。

• 您的初始化函数迭代一步太远，循环应为:

  for (int i = 0, number = 0; i < SIZE; i++) {
      array[i] = number;
      number += 2;
  }
  

• find() 确实应该返回找到的值的索引，如果找不到则返回 -1。你不返回任何东西。使其在失败时返回-1，在递归时返回递归调用的值。

• find 的参数是 start，范围的起始索引，包含在搜索中，end 上绑定(bind)，排除在搜索之外。在左侧部分递归时，不应传递 mid - 1。

修改后的版本:

#include <stdio.h>

#define SIZE 15

void fill_array(int array[], int size) {
    // here I just fill array with even numbers
    for (int i = 0, number = 0; i < SIZE; i++) {
        array[i] = number;
        number += 2;
    }
}

int find(int target, const int array[], int start, int end) {
    if (start >= end) {
        // empty range: not found
        return -1;
    }

    int mid = start + (end - start) / 2;

    if (target == array[mid]) {
        return mid;
    }
    if (target > array[mid]) {  
        return find(target, array, mid + 1, end);
    } else {
        return find(target, array, start, mid);
    }
}

void locate(int value, const int array[], int size) {
    int res = find(value, array, 0, size);
    if (res < 0) {
        printf("%d was not found in the array\n", value);
    } else {
        printf("%d was found at offset %d\n", value, res);
    }
}

int main(void) {
    int array[SIZE];

    fill_array(array, SIZE);
    locate(1, array, SIZE);
    locate(2, array, SIZE);
    return 0;
}

输出:

1 was not found in the array
2 was found at offset 1

请注意，find() 可以用更少的代码实现为循环:

int find(int target, const int array[], int start, int end) {
    while (start < end) {
        int mid = start + (end - start) / 2;

        if (target == array[mid]) {
            return mid;
        }
        if (target > array[mid]) {  
            start = mid + 1;
        } else {
            end = mid;
        }
    }
    return -1;
}