<分区>
这个问题不太可能帮助任何 future 的访问者；它只与一个小的地理区域、一个特定的时间点或一个非常狭窄的情况有关，这些情况并不普遍适用于互联网的全局受众。为了帮助使这个问题更广泛地适用，
visit the help center .
关闭 10 年前 。
int recurbinarysearch(int * oringalary, int low, int high, int target) {
if (low > high) {
return -1;
} else {
int mid = (low + high) / 2;
if (target == * (oringalary + mid)) return mid;
if (target > * (oringalary + mid)) return recurbinarysearch(oringalary, mid + 1, high, target);
if (target < * (oringalary + mid)) return recurbinarysearch(oringalary, low, mid - 1, target);
}
}
有人看到我的递归二分搜索算法有错误吗？偶尔它会返回一个不正确的索引(通常它会偏离一个)，但偶尔会偏离。然而，通常它是对的。我没有看到问题，希望得到帮助。
编辑 这是被接受的，所以我想我真的应该试着把它变成一个正确的答案。
我最初假设(请参阅下面的“注意 ”)该问题使用的是半开边界。它实际上(正确地)使用了包含 边界。在最初的通话中，low=0和 high=n-1 .
使用包含边界通常被认为是一件坏事 - 请在此处查看 Dijkstra 的经典著作 (PDF)。在 C 系列语言中，半开边界是一种常见的约定，甚至偏好 for (i = 0; i < n; i++)。在 for (i = 0; i <= n-1; i++) .但是，鉴于使用了包含边界，问题中的代码似乎是正确的。
不过，正如 WhozCraig 在评论中发现的那样，调用代码没有遵守该约定，并且传递了错误的边界 - 包括搜索范围内的越界垃圾项。由于该额外项是垃圾，因此范围内的项已排序的假设也可能无效。大多数搜索不会找到该垃圾项目(因为您不太可能搜索它具有的任何垃圾值)，但它会误导搜索。
注意 这可能不是答案，但对于评论来说太长了。
你的边界是包含的、排他的还是半开放的？
我将假设半开 - 包括 low , 独家 high .如果是这样，这条线看起来不对...
if (target < * (oringalary + mid))
return recurbinarysearch(oringalary, low, mid - 1, target);
原因是您检查了 mid 处的项目，但您使用的是 mid - 1作为您新的独有 上限。这意味着 mid - 1 处的项目，未被检查，被意外排除在搜索之外。该行应该是...
if (target < * (oringalary + mid))
return recurbinarysearch(oringalary, low, mid, target);
这使项目保持在 mid - 1在搜索范围内。 mid 处的项目不会再次搜索，因为上限是独占的。
在二进制搜索中搞乱边界是一个常见问题，它会导致比看起来更多的错误。
但是，这本身并不能解释您的症状 - 它应该经常找不到项目有时(可能占搜索的 50% 左右) 但它不应该报告错误的搜索位置成功了。
二进制搜索中错误边界的常见症状是无限循环(重复检查相同的项目，因为它没有被排除在边界之外)或搜索无法找到存在的项目(因为项目被排除在搜索范围之外未检查)。
老实说，我看不出你的症状是怎么出现的。函数退出的每一种可能方式都应该给出正确的成功结果，否则 -1失败的结果。我能想到的唯一可能的异常(exception)是在这段代码之外——误解结果，例如由于未能检查 -1结果。
顺便说一句 - 这是我重复我关于 one-comparison-per-iteration binary search 的问题和答案的绝好机会.
编辑 我想我发现了边界的另一个问题 - 仍然假设半开，这条线是错误的......
if (low > high) {
应该是……
if (low >= high) {
原因是对于半开边界，如果边界相等，则没有要检查的项目 - 即使是低边界项目也是无效的，因为高边界等于它并且互斥。这让你仍然可以测试