algorithm - 二进制搜索边界

Question

我在这方面总是遇到最困难的时候，而且我还没有看到对据称如此普遍和高度使用的东西的明确解释。

我们已经知道标准的二分查找。给定起始下限和上限，在 (lower + higher)/2 处找到中间点，然后将其与您的数组进行比较，然后相应地重新设置界限，等等。

然而，调整搜索以查找所需的差异是什么(对于按升序排列的列表):

1. 最小值 >= 目标
2. 最小值 > 目标
3. 最大值 <= 目标
4. 最大值<目标

似乎每种情况都需要对算法进行非常小的调整，但我永远无法使它们正常工作。我尝试改变不等式、返回条件，我改变边界的更新方式，但似乎没有什么是一致的。

处理这四种情况的 final方法是什么？

Answer 1

在我发现循环不变量和谓词是解决所有二元问题的最佳和最一致的方法之前，我遇到了完全相同的问题。

第 1 点:考虑谓词
一般来说，对于所有这 4 种情况(以及正常的二分查找相等性)，将它们想象成一个谓词。所以这意味着一些值满足谓词而一些不满足。例如，考虑这个目标为 5 的数组: [1、2、3、4、6、7、8]。查找第一个大于 5 的数字基本上等同于查找此数组中的第一个:[0, 0, 0, 0, 1, 1, 1]。

第 2 点:包含搜索边界
我喜欢两端始终包容。但我可以看到有些人喜欢开始包容和结束排他(在 len 而不是 len -1 上)。我喜欢将所有元素都放在数组中，所以在引用 a[mid] 时，我不认为这是否会给我一个超出范围的数组。所以我的偏好是:包容!!!

要点 3:While 循环条件 <=
所以我们甚至想在 while 循环中处理大小为 1 的子数组，并且当 while 循环结束时应该没有未处理的元素。我真的很喜欢这个逻辑。它总是坚如磐石。最初所有元素都不检查，基本上是未知的。这意味着 [st = 0, to end = len - 1] 范围内的所有内容都不会被检查。然后当 while 循环结束时，未检查元素的范围应该是大小为 0 的数组!

第 4 点:循环不变量
由于我们定义了 start = 0, end = len - 1，不变量将是这样的: start 剩下的任何东西都小于 target。 任何结束权大于或等于目标。

第 5 点:答案
一旦循环结束，基本上基于循环不变量，start 左边的任何东西都更小。所以这意味着开始是大于或等于目标的第一个元素。 等效地，end 右边的任何东西都大于或等于目标。所以这意味着答案也等于 end + 1。

代码:

public int find(int a[], int target){
  int start = 0; 
  int end = a.length - 1; 
  while (start <= end){
    int mid = (start + end) / 2; // or for no overflow start + (end - start) / 2
    if (a[mid] < target) 
       start = mid + 1; 
    else // a[mid] >= target
       end = mid - 1; 
  }
  return start; // or end + 1;
}

变化:
<强><
相当于找到第一个0。所以基本上只返回变化。

return end; // or return start - 1; 

>
将 if 条件更改为 <=，否则将是 >。没有其他变化。

<=
与 > 相同，return end; // or return start - 1;

所以一般来说，对于所有 5 种变体(<=、<、>、>=、正常二分查找)，只有 if 中的条件和 return 语句发生变化。当您考虑不变量(第 4 点)和答案(第 5 点)时，计算这些小的变化非常容易。

希望这能为阅读本文的人澄清。如果有任何不清楚的感觉，请联系我解释。理解了这个方法之后，二分查找就一清二楚了!

额外要点:最好也尝试包括开始但不包括结束。所以数组最初是 [0, len)。如果您可以编写不变量、while 循环的新条件、答案以及清晰的代码，则表示您了解了这个概念。