上界和下界的基本二进制搜索之间的区别？

Question

作者在文章http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=binarySearch中讨论了二分查找。他区分了寻找真实的最低值和错误的最高值。正在搜索的数组类似于：

假假假真真

我很好奇为什么这两种情况不同。为什么你不能只找到最低值是真的，然后减去一个找到最高值是假的？

Edit2：好的，所以我了解下限与上限。现在，我很难理解，在搜索大于或等于查询的最小整数时，为什么我们不能只将 if(mid>query) 更改为 if(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

.

Answer 1

如果数组永远是

false … true …

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

Answer 2

二分查找的下限和上限是可以在不破坏顺序的情况下插入值的最低和最高位置。（在 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

您引用的文章的作者用 "smaller than" 和 "greater than" 的等价词来表达所有这些，因此在搜索 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 编辑的迭代器 return 将引用 3 而来自 std::upper_bound 的迭代器将引用 4
在搜索 5 时，由 std::lower_bound 编辑的迭代器 return 将引用第一个 5 而来自 std::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 编辑的迭代器 return 跨越搜索范围内与搜索元素等效的元素范围。

如果元素不在范围内则此范围为空，这样lower_bound和upper_boundreturn是同一个迭代器，否则lower_boundreturn 是一个迭代器，它指向搜索范围内的第一个元素，它等于搜索值，而 upper_bound return 是一个迭代器，它指向最后一个元素后面的元素（如果有的话）。

Answer 3

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

请注意，尽管问题被标记为 C++，但代码示例不是 C++。因此它不是惯用的 C++。在 C++ 中实现类似 lower_bound() 或 upper_bound() 的典型方法是使用适当的迭代器。这些算法不会 "complain" 如果没有合适的元素，因为它们只会在适当的位置生成迭代器，即 std::lower_bound() 开始的迭代器和 std::lower_bound() 的尾后迭代器std::upper_bound().

上界和下界的基本二进制搜索之间的区别？

Difference between basic binary search for upper bound and lower bound?

c++

binary-search

lower-bound

upperbound