基本二进制搜索上限和下限之间的区别? [英] Difference between basic binary search for upper bound and lower bound?

问题描述

在文章 http://community.topcoder.com中/tc?module = Static& d1 = tutorials& d2 = binarySearch ，作者讨论了二进制搜索.他区分了在发现某物为真时的最低值与发现某物为假的最高值之​​间的区别. 正在搜索的数组类似于:

In the article http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=binarySearch, the author discusses binary search. He makes a distinction between finding the lowest value where something is true, and the highest value where something is false. The array being searched looks something like:

假假假真是

我很好奇为什么这两种情况不同.为什么不能只找到真实的最低值，然后减去一个就得出错误的最高值?

I am curious as to why these two cases are different. Why can't you just find the lowest value which is true, then subtract one to find the highest value which is false?

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

Ok, so I understand lower vs upper bound. Now, I am struggling to understand, when searching for the smallest integer greater than or equal to the query, why we can't just change the if(mid>query) to if(mid>=query) and have it do lower instead of upper bound.

这是文章所述:

"现在，我们终于到达实现二进制搜索的代码，如本节和上一节所述:

"Now we finally get to the code which implements binary search as described in this and the previous section:

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，我们将设计(使用与上述类似的原理):

If we wanted to find the last x for which p(x) is false, we would devise (using a similar rationale as above) something like:

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

."

推荐答案

二进制搜索的上下限是可以插入该值而不破坏顺序的最低和最高位置. (在C ++标准库中，这些界限将由迭代器表示，该迭代器引用可以在其之前插入值的元素，但实际上并没有改变概念.)

The lower and upper bound of a binary search are the lowest and highest position where the value could be inserted without breaking the ordering. (In the C++ standard library, these bounds will be represented by iterators referencing the element before which the value could be inserted, but the concept is not essentially changed.)

例如，以一个排序范围

1 2 3 4 5 5 5 6 7 9

在对3的二进制搜索中，我们将拥有

In a binary search for 3, we will have

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

然后在二进制文件中搜索5:

And in a binary search for 5:

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

如果范围中不存在该元素，则下限和上限相同.在二进制搜索中8:

The lower and upper bound are the same if the element does not exist in the range. In a binary search for 8:

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

您所引用的文章的作者用小于"和大于"的等效术语来表达所有这些，以便搜索5，

The author of the article to which you refer phrases all this in the equivalent terms of "smaller than" and "greater than" so that in a search of 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 ++迭代器都将引用直接位于边界后面的元素.就是说:

The C++ iterators will, in all these cases, refer to the element directly behind the bound. That is to say:

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

• In the search for 3, the iterator returned by std::lower_bound would refer to 3 and the one from std::upper_bound would refer to 4
• In the search for 5, the iterator returned by std::lower_bound would refer to the first 5 and the one from std::upper_bound would refer to 6
• In the search for 8, both would refer to 9

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

This is because the convention in the C++ standard library for insertions is to pass an iterator referring to the element before which the new element should be inserted. For example, after

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 would contain 1, 2, 3, 4, 5, 5, 5, 6, 7, 9. std::lower_bound and std::upper_bound follow this convention so that

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

根据需要工作，并保持vec排序.

work as desired and leave vec sorted.

更一般地，这是在C ++标准库中指定范围的方式的表达.范围的开始迭代器是指该范围的第一个元素(如果有)，而结束迭代器是指该范围末尾的元素(如果有).另一种看待它的方式是std::lower_bound和std::upper_bound返回的迭代器跨搜索范围内与搜索元素等效的元素范围.

More generally, this is an expression of the way ranges are specified in the C++ standard library. The beginning iterator of a range refers to the first element of the range (if any), while the ending iterator refers to the element (if any) directly behind the end of the range. Another way to look at it is that the iterators returned by std::lower_bound and std::upper_bound span the range of elements in the searched range that are equivalent to the searched element.

如果该元素不在该范围内，则此范围为空，因此lower_bound和upper_bound返回相同的迭代器，否则lower_bound返回一个迭代器，该迭代器引用搜索范围内等于upper_bound时的搜索值，返回一个迭代器，该迭代器引用的元素(如果有)直接位于最后一个此类元素的后面.

This range is empty if the element is not in the range, so that lower_bound and upper_bound return the same iterator, and otherwise lower_bound returns an iterator referring to the first element in the searched range that's equivalent to the search value while upper_bound returns an iterator referring to the element (if any) that's directly behind the last such element.

这篇关于基本二进制搜索上限和下限之间的区别?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！