二进制搜索边界

Question

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

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

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

最小值 >= 目标
最小值 > 目标值
最大值 <= 目标值
最大值 < 目标值

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

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

Answer 1

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

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]，因此我稍微修改了起始间隔。

Answer 2

基本的二分查找就是查找与目标键值相等的position/value。虽然它可以扩展到找到满足某些条件或的最小position/value找到满足某些条件.

的最大值position/value

假设数组是升序排列，如果没有满足position/value，return -1.

代码示例：

  // find the minimal position which satisfy some condition
  private static int getMinPosition(int[] arr, int target) {
      int l = 0, r = arr.length - 1;
      int ans = -1;
      while(l <= r) {
          int m = (l + r) >> 1;
          // feel free to replace the condition
          // here it means find the minimal position that the element not smaller than target
          if(arr[m] >= target) {
              ans = m;
              r = m - 1;
          } else {
              l = m + 1;
          }
      }
      return ans;
  }

  // find the maximal position which satisfy some condition
  private static int getMaxPosition(int[] arr, int target) {
      int l = 0, r = arr.length - 1;
      int ans = -1;
      while(l <= r) {
          int m = (l + r) >> 1;
          // feel free to replace the condition
          // here it means find the maximal position that the element less than target
          if(arr[m] < target) {
              ans = m;
              l = m + 1;
          } else {
              r = m - 1;
          }
      }
      return ans;
  }

    int[] a = {3, 5, 5, 7, 10, 15};
    System.out.println(BinarySearchTool.getMinPosition(a, 5));
    System.out.println(BinarySearchTool.getMinPosition(a, 6));
    System.out.println(BinarySearchTool.getMaxPosition(a, 8));

Answer 3

你需要的是一个二分查找，让你在最后一步参与到这个过程中。典型的二进制搜索将接收 (array, element) 并产生一个值（通常是索引或 not found）。但是如果你有一个修改过的二进制文件，它接受一个在搜索结束时调用的函数，你就可以涵盖所有情况。

比如在Javascript为了方便测试，下面的二分查找

function binarySearch(array, el, fn) {
    function aux(left,  right) {
        if (left > right) {
            return fn(array, null, left, right);
        }

        var middle = Math.floor((left + right) / 2);
        var value = array[middle];

        if (value > el) {
            return aux(left, middle - 1);
        } if (value < el) {
            return aux(middle + 1, right);
        } else {
            return fn(array, middle, left, right);
        }
    }

    return aux(0, array.length - 1);
}

将允许您使用特定的 return 函数涵盖每个案例。

默认
function(a, m) { return m; }
最小值 >= 目标
function(a, m, l, r) { return m != null ? a[m] : r + 1 >= a.length ? null : a[r + 1]; }
最小值 > 目标值
function(a, m, l, r) { return (m || r) + 1 >= a.length ? null : a[(m || r) + 1]; }
最大值 <= 目标值
function(a, m, l, r) { return m != null ? a[m] : l - 1 > 0 ? a[l - 1] : null; }
最大值 < 目标值
function(a, m, l, r) { return (m || l) - 1 < 0 ? null : a[(m || l) - 1]; }

Answer 4

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

要点 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变化。

return end; // or return start - 1;

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

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

因此，对于所有 5 种变体（<=、<、>、>=、正常二分搜索），通常只有 if 中的条件和 return 语句发生变化。当您考虑不变量（第 4 点）和答案（第 5 点）时，计算这些小的变化非常容易。

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

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

二进制搜索边界

Binary search bounds

algorithm

binary-search