C 中的二分搜索,递归函数仅接受长度
我正在解决“编程珍珠”练习。 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 并计算偏移量。
但这似乎很复杂。你能找到更好的解决方案吗?
I am solving "Programming Pearls" exercises. 4.11 say:
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.
I came up with:
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);
}
However - there is problem. I return the offset including array address because otherwise how to know the relative offset of the element to original array?
So I need this wrapper:
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);
}
It's not recursive - it just calls bsearch_rec_array_only
and computes offset.
But this seems complicated. Can you find a better solution?
如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱,如果其他用户或者作者回复了您的评论,将不能在第一时间通知您!
发布评论
评论(2)
您的问题是代码不返回元素相对于数组开头的偏移量,而是返回一个转换为 int 的指针。您使用强制转换的事实应该表明代码中存在问题。
尝试返回一个偏移量。像这样的东西:
Your problem is that the code doesn't return the offset of the element from the array's beginning, but a pointer cast into an int. The fact that you used a cast should show you that there something's wrong in the code.
Try returning an offset. Something like this:
这是正确的答案:
Here is the correct answer: