我正在解决“编程珍珠”练习。4.11 说:
使用以下声明编写并证明 C 或 C++ 中递归二进制搜索函数的正确性:
int binarysearch(DataType x[], int n);
单独使用此功能;不要调用任何其他递归函数。
我想出了:
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
和计算偏移量。
但这似乎很复杂。你能找到更好的解决方案吗?