前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >lower_bound 和 upper_bound 功能和用法

lower_bound 和 upper_bound 功能和用法

作者头像
_DIY
发布2019-09-11 17:26:47
9010
发布2019-09-11 17:26:47
举报
文章被收录于专栏:用户6093955的专栏

以前用这两个函数的时候,简单看了几句别人的博客,记住了大概,用的时候每用一次就弄混一次,相当难受,今天对照着这两个函数的源码和自己的尝试发现:其实这两个函数只能用于 “升序” 序列。

为什么还要加个引号呢?因为比较规则可以自定义,如果你非要把比较规则定义成 5 比 3 小,那么 降序序列也是可以用的,否则不可以,直接看下例子(这是升序序列的 ):

代码语言:javascript
复制
#include<bits/stdc++.h>
using namespace std;
int main() 
{
    int a[] = {1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4};
    cout << (lower_bound(a, a + 12, 4) - a) << endl; //输出 9
    cout << (upper_bound(a, a + 12, 4) - a) << endl; //输出 12
    cout << (lower_bound(a, a + 12, 1) - a) << endl; //输出 0
    cout << (upper_bound(a, a + 12, 1) - a) << endl; //输出 3
    cout << (lower_bound(a, a + 12, 3) - a) << endl; //输出 6
    cout << (upper_bound(a, a + 12, 3) - a) << endl; //输出 9
    cout << (lower_bound(a, a + 12, 5) - a) << endl; //输出 12
    cout << (upper_bound(a, a + 12, 5) - a) << endl; //输出 12
    cout << (lower_bound(a, a + 12, 0) - a) << endl; //输出 0
    cout << (upper_bound(a, a + 12, 0) - a) << endl; //输出 0
    return 0;
}

不出所料,在对 4 进行 lower_bound 时,输出结果是 9,因为在升序序列中 lower_bound 返回第一个大于等于 参数val 的 序列值的迭代器,这里 val 为 4,lower_bound 进行二分查找,找到第一个 4 时符合条件所以返回(确切的说当步长减到 0 时,欲返回的这个迭代器会停在第一个 4 那里),然后减去首迭代器 a,就是两个迭代器的距离了(在这里也就是数组中下标),第一个 4 的下标是 9。在对 4 进行 upper_bound 时,输出结果是 12,因为在升序序列中 upper_bound 返回第一个大于 参数val 的 序列值的迭代器,不幸的是这个序列里找不到大于 4 的值,所以迭代器走到尽头也没有找到,于是返回了一个尾迭代器(在这里是数组越界后的那一个元素的指针),它在数组中下标为 12 。同理可以对剩下的那几个分析。

那么如果是降序序列呢?如果是降序序列,这个函数仍然以为你这个序列是升序的,我们以{4,4,4,3,3,3,2,2,2,1,1,1}作为例子,试验一下。

代码语言:javascript
复制
#include<bits/stdc++.h>
using namespace std;
int main() 
{
    int a[] = {4, 4, 4, 3, 3, 3, 2, 2, 2, 1, 1, 1};

    cout << (lower_bound(a, a + 12, 4) - a) << endl; // 输出 12
    cout << (upper_bound(a, a + 12, 4) - a) << endl; // 输出 12
    cout << (lower_bound(a, a + 12, 1) - a) << endl; // 输出 0
    cout << (upper_bound(a, a + 12, 1) - a) << endl; // 输出 0
    cout << (lower_bound(a, a + 12, 3) - a) << endl; // 输出 12
    cout << (upper_bound(a, a + 12, 3) - a) << endl; // 输出 12

    return 0;
}

不难发现,这两个函数的输出结果都很无厘头,不是期望的结果,那么为什么会这样呢?刚才说了,这个函数仍然以为你这个序列是升序的,以这句为例 lower_bound(a, a + 12, 4) ,因为是二分查找,第一步从中间开始,取中间值 a[(0+12)/2] = a[6] = 2 ,比 4 小,但是他想要找到第一个大于等于 4 的,所以继续向更大的值靠近,向哪边靠近呢,右边,因为他以为你这是升序的,所以取右半部分中间值 a[(7+12)/2] = a[9] = 1,比 4 小,所以继续向更大的值靠近,取右半部分中间值 a[(10+12)/2] = a[11] = 1,比 4 小,所以继续向更大的值靠近,取右半部分中间值 a[(12+12)/2] = a[12],到这不用取了,到头了,该返回了,所以最终返回了尾迭代器。

对照一下它的一个可能的实现源码,或许有助于理解。

这个 iterator_traits<ForwardIterator>::difference_type 其实就是个 int 类型,只是另起了一群其他名字,distance 函数是计算两个迭代器之间距离,advance 函数是将参数1(迭代器类型)前进 step 步,剩下的就没有什么不认识的东西了。

代码语言:javascript
复制
template <class ForwardIterator, class T>
  ForwardIterator lower_bound (ForwardIterator first, ForwardIterator last, const T& val)
{
  ForwardIterator it;
  iterator_traits<ForwardIterator>::difference_type count, step;
  count = distance(first, last);
  while(count > 0)
  {
    it = first; step = count / 2; 
    advance(it, step);
    if (*it < val) { // or: if (comp(*it,val)), for version (2)
      first = ++it;
      count -= step + 1;
    }
    else 
      count = step;
  }
  return first;
}

转载自: --------------------- 作者:锦夏挽秋 来源:CSDN 原文:https://blog.csdn.net/qq1337715208/article/details/81072709

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2019-05-26 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档