二分搜索算法的问题

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] 包含在右边。如果出现vbefore middle，我们将在后续迭代中找到它们。

• 作为旁注，更自然的定义[0, n)包含在左侧，排除在右侧，可用于查找v.

以我的经验，这种包容-排斥的区间定义产生了最短、最清晰和最通用的代码。人们一直在努力改进它，但他们经常陷入困境。