二分查找边界

Question

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

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

但是，调整搜索以查找所需的差异是什么（对于按升序排列的列表）：

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

似乎这些情况中的每一个都需要对算法进行非常小的调整，但我永远无法让它们正常工作。我尝试更改不等式、返回条件、更改边界的更新方式，但似乎没有任何一致。

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

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] 时，我不认为这是否会给我一个越界的数组。所以我的偏好：包容！！！

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

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

第 5 点：答案
一旦循环结束，基本上基于循环不变量，start 左边的任何东西都更小。所以这意味着 start 是第一个大于或等于目标的元素。等效地，末尾右侧的任何内容都大于或等于目标。所以这意味着答案也等于 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 点）时，计算这些小的变化非常容易。

希望这对阅读本文的人有所澄清。如果有什么不清楚的感觉像魔术，请 ping 我来解释。了解了这个方法，二分查找的一切就应该一清二楚了！

额外的一点：尝试包括开始但不包括结束将是一个很好的做法。所以数组最初是 [0, len)。如果你能写出不变量、while 循环的新条件、答案和清晰的代码，就意味着你学会了这个概念。

Answer 2

二分搜索（至少是我实现它的方式）依赖于一个简单的属性 - 谓词对于区间的一端成立，而对于另一端不成立。我总是认为我的区间一端是封闭的，另一端是开放的。那么让我们看一下这段代码：

int beg = 0; // pred(beg) should hold true
int end = n;// length of an array or a value that is guranteed to be out of the interval that we are interested in

while (end - beg >  1) {
  int mid = (end + beg) / 2;
  if (pred(a[mid])) {
    beg = mid;
  } else { 
    end = mid;
  }
}
// answer is at a[beg]

这适用于您定义的任何比较。只需替换pred为<=target或>=target或<target或>target。

循环退出后，a[beg]将是给定不等式成立的最后一个元素。

因此，让我们假设（就像评论中建议的那样）我们想要找到 的最大数字a[i] <= target。那么如果我们使用谓词，a[i] <= target代码将如下所示：

int beg = 0; // pred(beg) should hold true
int end = n;// length of an array or a value that is guranteed to be out of the interval that we are interested in
while (end - beg >  1) {
  int mid = (end + beg) / 2;
  if (a[mid] <= target) {
    beg = mid;
  } else { 
    end = mid;
  }
}

循环退出后，您要查找的索引将为 beg。

另外，根据比较，您可能必须从数组的右端开始。例如，如果您正在搜索最大值 >= 目标，您将执行以下操作：

beg = -1;
end = n - 1;
while (end - beg >  1) {
  int mid = (end + beg) / 2;
  if (a[mid] >= target) {
    end = mid;
  } else { 
    beg = mid;
  }
}

您正在搜索的值将包含在索引中end。请注意，在这种情况下，我考虑了间隔(beg, end]，因此我稍微修改了起始间隔。