0

在二分查找算法中，上界元素是array.length-1，那么如何找到数组的最后一个元素呢？

如果长度为 8 的数组元素的下限和上限分别为 6 和 7，那么我的中间元素输出为：

mid=(6+7)/2 即java中的6

4

5 回答 5

5

它实际上归结为使用正确的比较与正确选择的中点。例如（没有变量类型声明），

binsearch(a,val,left,right){
    if(left==right) return left;
    mid = (left+right)/2;
    if(a[mid] < val)
        return binsearch(a,val,mid+1,right);
    else
        return binsearch(a,val,left,mid);
}

将为您提供与 val 匹配的最左边元素的索引（即使它是数组中最右边的元素）。您不需要显式检查最后两个或向上取整，而不需要使用内置的整数截断。

但是，如果您想要等于 val 的最右边元素的索引，那么您需要将 < 运算符更改为 > 并且 mid 应该由

mid = (left+right+1)/2;

就这么简单。

编辑：还有一件事，我查看了我用于此的代码，并意识到您还必须更改对 binsearch 的调用以结束最右边的元素。我将为此发布完整的代码（我应该首先完成）。这是一个二进制搜索来找到等于 val 的最右边的元素。

binsearch(a,val,left,right){
    if(left==right) return left;
    mid = (left+right+1)/2;
    if(a[mid] > val)
        return binsearch(a,val,left,mid-1);
    else
        return binsearch(a,val,mid,right);
}
于 2010-02-14T07:01:44.527 回答
2

最简单的方法是使用半开范围。这样，您的上限指向数组中最后一个有效项之后的一步，尽管您的下限直接指向第一项。但是，在搜索期间，您将您的范围视为包含范围 - 超出范围的上限是有效的“未找到匹配”结果。

在每次迭代开始时，您有...

lower <= target <= upper

“目标”表示将被找到并返回的索引。

您将 mid 计算为“（上 + 下）/2”。由于这会截断，所以 mid 永远不能与 upper 相同，这很重要。由于“upper”可能越界，我们永远不能合法地评估“array [upper]”。

要查找大于或等于键的第一项...

if array[mid] >= k :  lower <= target <= mid
if array[mid] <  k :  mid+1 <= target <= upper

要找到第一个大于键的项目...

if array[mid] >  k :  lower <= target <= mid
if array[mid] <= k :  mid+1 <= target <= upper

这些子范围是包容性的，并且必须精确地相遇但不能重叠。中间的单个项目重叠（一个容易的错误）会导致无限循环，这也是我们将 mid+1 用于一个子范围的部分原因。

请注意，两次搜索之间的所有变化都是比较运算符。

要找到最后一个小于或等于，请找到第一个大于并从结果中减去一个。如果数组中的所有项目都大于键，则可以得到 -1。

注意 - 您只在每次迭代中针对 mid 测试 key（您知道下限和上限已经是正确的）并且您只进行一次条件测试。

在循环之外进行越界检查和相等检查（如果这是您需要的） 。

int find_first_ge (int key)
{
  int lower = 0;
  int upper = array.length;

  while (upper > lower)
  {
    int mid = (lower + upper) / 2;

    if (array [mid] >= key)  //  for find_first_gt, use ">" here
    {
      upper = mid;
    }
    else
    {
      lower = mid + 1;
    }
  }

  return lower;
}

笔记

编辑以纠正一些错误，这些错误与它原本要修复的内容一样无限循环。

诀窍是确保在每次关键测试后二等分的子范围完全符合需要，并且始终至少比原始完整范围小一个 - 由于过度自信和糟糕的记忆，这正是我设法弄错的地方。以上基于大量使用的库中的真实工作代码（在多路树库中的节点内搜索），所以如果它错了，我就会遇到大问题;-)

笔记

再次编辑以改进措辞并简化子范围边界描述（注意虽然范围是半开的，但它们被视为包含在内）。

于 2010-02-14T06:43:08.300 回答
0

当您的下限和您的上限彼此在一个范围内时，请同时检查两者。

于 2010-02-14T06:19:32.787 回答
0

众所周知，二分搜索很难完全正确。在Programming Pearls中对各种问题和边缘案例进行了非常彻底的分析，以及正确的实现，这本书每个程序员都应该至少读过一次。

于 2010-02-14T08:19:49.273 回答
0

你可以每次四舍五入。

(6+7)/2.0 == 6.5

将其四舍五入，您将得出 7。

或者你可以简单地在你的中点上加一个。

中 = (6+7)/2 + 1

另一种方法是将您的起点或终点更改为 +1 或 -1 以进行以下递归。这是关于该主题的维基百科文章在某些实现中显示的内容。

最小值 = 中 + 1

或者

最大值 = 中 1

于 2010-02-14T06:14:20.790 回答