二进制搜索算法的问题

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，因此扔掉了右半边。这样做是安全的，因为我们不关心任何v过去的middle。我们关心arr[middle]，这可能是也可能不是第一次出现，正是由于这个原因，我们将（lo，hi）包容在右边。如果在v之前有middle的出现，我们会在随后发现它们迭代。
• 作为旁注，左侧包含的更自然的定义[0, n)，右侧独有，可用于查找v的最后一次出现。

根据我的经验，这种包容性的独占区间定义产生了最短，最清晰和最通用的代码。人们不断努力改进它，但他们经常在角落里纠结。