二分查找边界

Question

我总是在这个问题上遇到最大的困难，而且我还没有看到一个明确的解释，即使这是一个被认为非常普遍和高度使用的东西。

我们已经知道了标准的二分查找。给定起始的下边界和上边界，找到中间点（lower + higher）/ 2，并与数组进行比较，然后相应地重新设置边界等等。

但是，如何调整搜索以查找（对于一个升序列表）：

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

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

如何处理这四种情况的明确方法是什么？

- user4992519

---

我不明白这个问题；“最小值”和“最大值”是数组中最左侧和最右侧位置的值吗？ - Codor

这是一道作业题吗？否则问起来有点奇怪。 - StilesCrisis

@StilesCrisis 一点也不是。这只是我一遍又一遍遇到的问题。 - user4992519

@Codor 是的，抱歉。假设数组按升序排序。 - user4992519

你是在问如果目标不在数组中，它是如何工作的吗？ - JShell

Answer 1

我发现循环不变量和谓词是处理所有二进制问题的最佳和最一致的方法。

要点1：考虑谓词 对于所有这4种情况（以及正常的二进制搜索相等性），将它们想象成一个谓词。这意味着一些值符合谓词，而一些值不符合。例如，考虑这个目标为5的数组： [1, 2, 3, 4, 6, 7, 8]。找到第一个大于5的数字基本上等同于在这个数组中找到第一个1：[0, 0, 0, 0, 1, 1, 1]。

要点2：搜索边界包含 我喜欢两端都包含。但我知道有些人喜欢起始点包含而结束点不包含（在长度上而不是长度-1上）。我喜欢将所有元素都放在数组内部，这样在引用a[mid]时，我不用担心是否会超出数组范围。所以我的偏好是：包含！

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

第四点：循环不变量 由于我们定义了start = 0，end = len - 1，不变量将会是这样的： start左边的任何元素都小于目标值。 end右边的任何元素都大于或等于目标值。

第五点：答案 一旦循环结束，基于循环不变量，start左边的任何元素都小于目标值。所以这意味着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; // 或 return start - 1;

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

理解了这种方法之后，二分查找的一切都应该清晰明了！

额外的一点：尝试包括起始位置但不包括结束位置也是一个很好的实践。因此，数组最初将为[0，len)。如果您能编写不变量、while循环的新条件、答案以及清晰的代码，那就意味着您已经掌握了这个概念。

- apadana

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

- Ivaylo Strandjev

---

你能举个例子来详细说明你的意思吗？例如谓词。 - user4992519

那么谓词必须为假？难道没有几种方法可以做到这一点吗？我认为这可能是一个强有力的答案，但我只是不理解这种方法。 - user4992519

它在哪个意义上不准确？你能提供一个具体的例子吗？ - Ivaylo Strandjev

@user4992519 我明白了，这很有道理。我的算法确保索引为 beg 的值满足谓词条件。因此，第一个不满足谓词条件的值实际上是数组中的下一个值（请注意检查没有这样的数字的情况）。 - Ivaylo Strandjev

让我们在聊天中继续这个讨论。 - Ivaylo Strandjev

Answer 3

基本的二分查找是为了查找与目标键相等的位置/值。虽然它可以扩展到查找满足某些条件的最小位置/值，或者查找满足某些条件的最大位置/值。

假设数组是升序的，如果没有找到满足条件的位置/值，则返回-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));

- coderz

---

@user4992519，你能粘贴你的测试用例吗？ - coderz

Answer 4

你需要的是一种二分查找算法，它可以让你在最后一步参与进来。典型的二分查找会接收一个数组和一个元素，并产生一个值（通常是索引或“未找到”）。但如果你有一个修改过的二分查找算法，在搜索结束时接受一个函数进行调用，那么你就可以涵盖所有情况。

例如，在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);
}

可以让您使用特定的返回函数来处理每种情况。

• 默认值
  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]; }

- m4ktub