首页 文章

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

提问于
浏览 次
11

在文章http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=binarySearch中，作者讨论了二进制搜索 . 他区分了找到某些东西是真的最低值，以及某些东西是假的最高值 . 被搜索的数组看起来像：

false false false true true

我很好奇为什么这两个案例不同 . 为什么你不能找到真实的最低值，然后减去一个找到最高值，这是假的？

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

“ .

c++ binary-search lower-bound upperbound

3 回答

  • 0

    二进制搜索的下限和上限是可以插入值的最低和最高位置，而不会破坏排序 . （在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 返回迭代器引用到最后一个元素后面的元素（如果有的话） .

    回复于
  • 1

    如果数组将永远

    false … true …

    然后，除非您在 index 0 找到true，否则您找到的索引之前的索引将始终为false . 如上面的评论中提到的另一个边界情况是，如果找不到 true . 然后，最高的false将是数组的最后一部分 .

    回复于
  • 34

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

    请注意，代码示例不是't C++ despite the question being tagged C++. As a result it isn' t idiomatic C . C中实现类似 lower_bound() 或 upper_bound() 的典型方法是使用适当的迭代器 . 这些算法不会产生迭代器的适当位置，即 std::lower_bound() 的起始迭代器和 std::upper_bound() 的过去迭代器 .

    回复于

相关问题