18

在文章http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=binarySearch中，作者讨论了二分搜索。他区分了找到某事为真的最低值和某事为假的最高值。正在搜索的数组看起来像：

假 假 假 真 真

我很好奇为什么这两种情况不同。为什么你不能只找到正确的最小值，然后减去一个以找到错误的最大值？

Edit2：好的，所以我理解下限和上限。现在，我很难理解，在搜索大于或等于查询的最小整数时，为什么我们不能只更改if(mid>query)toif(mid>=query)并让它做下限而不是上限。

编辑：这是文章所说的：

“现在我们终于得到了实现二进制搜索的代码，如本节和上一节所述：

binary_search(lo, hi, p):
   while lo < hi:
      mid = lo + (hi-lo)/2
      if p(mid) == true:
         hi = mid
      else:
         lo = mid+1

   if p(lo) == false:
      complain                // p(x) is false for all x in S!

   return lo         // lo is the least x for which p(x) is true

...

如果我们想找到 p(x) 为假的最后一个 x，我们会设计（使用与上述类似的原理）类似的东西：

binary_search(lo, hi, p):
   while lo < hi:
      mid = lo + (hi-lo+1)/2    // note: division truncates
      if p(mid) == true:
         hi = mid-1
      else:
         lo = mid

   if p(lo) == true:
      complain                // p(x) is true for all x in S!

   return lo         // lo is the greatest x for which p(x) is false

。”

4

3 回答 3

52

二分搜索的下限和上限是可以在不破坏顺序的情况下插入值的最低和最高位置。（在 C++ 标准库中，这些边界将由引用可以插入值的元素的迭代器来表示，但这个概念本质上并没有改变。）

举个例子，一个排序的范围

1 2 3 4 5 5 5 6 7 9

在对 的二分搜索中3，我们将有

   v-- lower bound
1 2 3 4 5 5 5 6 7 9
     ^-- upper bound

并在二进制搜索中5：

       v-- lower bound
1 2 3 4 5 5 5 6 7 9
             ^-- upper bound

如果元素不存在于范围内，则下限和上限相同。在二进制搜索中8：

                 v-- lower bound
1 2 3 4 5 5 5 6 7 9
                 ^-- upper bound

您引用的文章的作者用“小于”和“大于”的等效术语来表达所有这些，因此在搜索 5 时，

       v-- lower bound
t t t t f f f f f f      <-- smaller than?
1 2 3 4 5 5 5 6 7 9
f f f f f f f t t t      <-- greater than?
             ^-- upper bound

在所有这些情况下，C++ 迭代器将直接引用边界后面的元素。也就是说：

  • 在搜索中3，由返回的迭代器std::lower_bound将引用，3而来自的迭代器std::upper_bound将引用4
  • 在搜索中5，返回的迭代器std::lower_bound将引用第一个5，而 fromstd::upper_bound将引用6
  • 在搜索中8，两者都指9

这是因为 C++ 标准库中的插入约定是传递一个迭代器，该迭代器引用应该在其之前插入新元素的元素。例如，之后

std::vector<int> vec { 1, 3, 4, 5, 5, 5, 6, 7, 9 };
vec.insert(vec.begin() + 1, 2);

vec将包含1, 2, 3, 4, 5, 5, 5, 6, 7, 9. std::lower_bound并std::upper_bound遵循这个约定，以便

vec.insert(std::lower_bound(vec.begin(), vec.end(), 5), 5);
vec.insert(std::upper_bound(vec.begin(), vec.end(), 8), 8);

根据需要工作并vec排序。

更一般地说，这是在 C++ 标准库中指定范围的方式的一种表达方式。范围的开始迭代器是指范围的第一个元素（如果有），而结束迭代器是指直接在范围末尾后面的元素（如果有）。另一种看待它的方法是迭代器返回std::lower_bound并std::upper_bound跨越搜索范围内与搜索元素等效的元素范围。

如果元素不在范围内，则此范围为空，因此lower_bound和upper_bound返回相同的迭代器，否则lower_bound返回一个迭代器，该迭代器引用搜索范围内的第一个元素，相当于搜索值，同时upper_bound返回一个引用该元素的迭代器 (如果有的话）直接在最后一个这样的元素后面。

于 2015-02-08T00:28:17.587 回答
1

如果数组总是

false … true …

那么你找到的索引之前的索引将永远是假的，除非你在index 0. 正如我在上面的评论中提到的，另一个边界情况是如果你没有找到true. 然后，最高的 false 将是数组的最后一部分。

于 2015-02-08T00:16:15.467 回答
0

true这两种算法在没有值或没有值时应该发生的情况明显不同，这false在代码片段中实际上很明显：如果您找到值所在的最低值true并从该位置减去 1 以找到最高值false由于没有这样的对象，因此会产生产生不正确结果的值。由于算法只是针对不同的元素直接定位适当的元素而不是具有特殊情况，因此也避免了必须处理特殊情况，从而减少了代码量。由于特殊情况代码往往只为每个算法调用执行一次，因此它的执行可能比避免特殊情况稍差。这可能是值得衡量的。

请注意，尽管问题被标记为 C++，但代码示例不是 C++。因此，它不是惯用的 C++。C++ 中实现类似lower_bound()or的典型方法upper_bound()是使用适当的迭代器。如果没有合适的元素，这些算法不会“抱怨”，因为它们只会在适当的位置产生一个迭代器，即一个迭代器开始 forstd::lower_bound()和一个过去的迭代器 for std::upper_bound()。

于 2015-02-08T00:35:26.433 回答