c - C中的二进制搜索，递归函数只接受长度

Question

我正在解决“编程珍珠”练习。 4.11 说:

Write and prove the correctness of a recursive binary search function in C or C++ with this declaration:

int binarysearch(DataType x[], int n);

Use this function alone; do not call any other recursive function.

我想到了:

int bsearch_rec_array_only(int key, int* arr, int n)
{
    int mid;

    if (n < 0)
        return -1;

    mid = n / 2;

    if (arr[mid] == key)
        return (int) ((size_t) arr + mid * sizeof(*arr));
    else if (arr[mid] < key)
        return bsearch_rec_array_only(key, arr + mid + 1, n - mid - 1);
    else
        return bsearch_rec_array_only(key, arr, mid - 1);
}

但是 - 有问题。我返回包含数组地址的偏移量，否则如何知道元素相对于原​​始数组的相对偏移量？

所以我需要这个包装器:

int bsearch_array_only_wrap(int key, int* arr, int n)
{
    int offset;
    if (n == 0)
        return -1;

    offset = bsearch_rec_array_only(key, arr, n);

    if (offset == -1)
        return -1;
    else       
        return (offset - (int) arr) / sizeof(*arr);
}

它不是递归的 - 它只是调用 bsearch_rec_array_only 并计算偏移量。

但这看起来很复杂。你能找到更好的解决方案吗？

Answer 1

你的问题是代码不返回元素从数组开始的偏移量，而是一个转换为 int 的指针。您使用强制转换这一事实应该表明代码中有问题。

尝试返回一个偏移量。像这样:

if (arr[mid] == key)
        return mid;
else if (arr[mid] < key) {
        int i = bsearch_rec_array_only(key, arr + mid + 1, n - mid - 1);
        return (i != -1) ? i + mid + 1 : -1;
} else
        return bsearch_rec_array_only(key, arr, mid - 1);