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

Question

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

假假假真真

我很好奇，为什么这两种情况是不同的。为什么你不能找到真正的最低值，然后减去一个来找出最高的值是错误的？编辑2：好的，所以我理解更低的上限。现在，我在努力理解，当搜索大于或等于查询的最小整数时，为什么我们不能将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 

...

如果我们想找到最后x其中p（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

二进制搜索的下限和上限是可以在不破坏顺序的情况下插入值的最低和最高位置。 （在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和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返回的迭代器跨越搜索范围中等于搜索元素的元素范围。

这个范围是空的，如果该元素不在范围内，使lower_bound和upper_bound返回相同的迭代器，否则lower_bound返回一个迭代器，在搜索范围内的第一个元素是等同于同时upper_bound搜索值返回一个指向最后一个元素后面的元素（如果有的话）的迭代器。如果你找到最低值，其中值是true和减去1：

Answer 2

如果阵列将永远是

false … true … 

那么一个你会发现永远是假的，除非你在index 0找到真正的前指数。如上面我的评论所述，另一个边界案例是，如果您没有找到true。然后，最高的false将是数组的最后一部分。

Answer 3

这两种算法中，如果有任何true或没有false值从代码片段其实是相当明显的应发生什么情况明显不同从这个位置找到最高值产生false产生了不正确的结果，因为没有这样的对象。由于算法只针对处理定位适当元素的不同元素而不是特殊情况，因此也避免了必须处理特殊情况，从而减少了代码量。由于特殊情况代码往往只对每个算法调用执行一次，因此它可能会比避免特殊情况稍差。这是值得衡量的事情。

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