java - 二进制搜索算法的问题

Question

我有一个任务要编写一个二分查找，它返回我们要查找的值的第一次迭代。我一直在网上做一些研究，我的搜索看起来很像我正在寻找的东西，但我遇到了问题。如果我向这段代码传递一个看起来像 {10,5,5,3,2} 的数组，它会在中间找到 5(它检查的第一件事)，然后返回它。但这不是 5 的第一次迭代，而是第二次。我究竟做错了什么？这可能吗？

提前致谢!

代码(我用的是Java):

public static int binarySearch(int[] arr, int v){
    int lo = 0;
    int hi = arr.length-1;
    while(lo <= hi){
        int middle = (lo+hi)/2;
        if(v == arr[middle]){
            return middle;
        }
        else
        {
            if(v < arr[middle]){
                lo = middle+1;
            }  
            else
            {
                hi = middle-1;
            }
        }
    }
    return -1;
}

Answer 1

这是一个修改后的有效算法。

public static int binarySearch(int[] arr, int v) {
  int lo = -1;
  int hi = arr.length - 1;

  while (hi - lo > 1 ) {
    int middle = (lo + hi) / 2;
    if (arr[middle] > v) {
      lo = middle;
    } else {
      hi = middle;
    }
  }

  if (v == arr[hi]) {
    return hi;
  } else {
    return -1;
  }
}

关键点是:

• 区间(lo, hi]左独右含。
• 在每一步，我们都丢掉一半的间隔。当我们只剩下一个元素时，我们就停下来。尝试提前终止只能提供最小的性能提升，而它们通常会影响代码的易读性和/或引入错误。
• 当 arr[middle] = v 时，我们分配 hi = middle，从而丢弃右半部分。这样做是安全的，因为我们不关心 middle 之后出现的任何 v。我们确实关心 arr[middle]，它可能是也可能不是第一次出现，正是出于这个原因，我们将 (lo, hi] 包含在右边。如果出现v在middle之前，我们会在后续的迭代中找到它们。
• 附带说明，更自然的定义 [0, n) 包含在左边，不包含在右边，可用于查找最后一次出现的 v.

根据我的经验，这种包含 - 排他间隔定义会产生最短、最清晰和最通用的代码。人们一直在努力改进它，但他们经常会陷入极端情况。