精华内容
下载资源
问答
  • 首先先讲一下什么时候不能用upper_boundlower_bound函数:当题目是一道以二分搜索算法为核心的题目时,这种时候一般会设置数据把这两个函数卡掉,所以我们经量用手打的二分搜索。 而一般我们用二分搜索来优化一个...

    首先先讲一下什么时候不能用upper_bound和lower_bound函数:当题目是一道以二分搜索算法为核心的题目时,这种时候一般会设置数据把这两个函数卡掉,所以我们经量用手打的二分搜索。
    而一般我们用二分搜索来优化一个算法的时候,比如线段树需要离散一下点,排序后需要二分点找离散值,这种时候就可以使用二分搜索函数。

    lower_bound的第三个参数传入一个元素x,在两个迭代器(或指针)指定的部分上执行二分查找,返回指向第一个大于等于x的元素的位置的迭代器(或指针)。

    upper_bound的用法和lower_bound大致相同,唯一的区别是查找第一个大于x的元素。当然,两个迭代器(或指针)指定的部分应该是提前排好序的。

    需要注意的是如果原来的序列中就有一个或多个x,那么lower是找到大于等于第一个x的位置。而upper是插入最后一个x后面的位置。

    • 在有序int数组(元素存放在下标1-n)中查找大于等于x的最小整数的下标
    int i=lower_bound(a+1,a+n+1)  -  a;
    
    • 如果是查找具体的数值
    int ans = *lower_bound(a+1,a+1+n,N);
    

    以上内容均转载于狠人王 对lower_bound/upper_bound 二分的介绍

    二分的时间复杂度为O(logn),n为序列长度。

    需要注意的是,mid的取值不要写成(l + r) / 2,因为如果l + r很大的话,会溢出。因此写成l +(r - l)/2就不会有这个问题
    更进一步,当然也可以用位运算来l +((r - l)>>1)代替(这里要注意是先除以2,再加上l!!+的优先级要比>>高,所以要加括号),而且这种位运算的效率更高一些。

    手写二分函数:

    • 数组中存在重复的数据,怎么找出元素最后一次出现的位置 和上边介绍的二分查找思路一样:
       int upper_bound(int key)
    {
    	int l = 1, r = p;
    	while(l <= r)
    	{
    		int mid = l + ((r-l)>>1);
    		if(key >= sum2[mid])    //upper的话等于的时候也返
    		                 //回右边,因为要找到大于最后一个key。
    		  l = mid + 1;
    		else 
    		  r = mid - 1;
    	}
    	return l;       //记得返回L。
    }
    
    int lower_bound(int key)
    {
    	int l = 1, r = p;
    	while(l <= r)
    	{
    		int mid = l + ((r-l)>>1);
    		if(key > sum2[mid])     
    		  l = mid + 1;
    		else             //lower相等时候就返回左边,因为要
    		                //找到第一个key。
    		  r = mid - 1;
    	}
    	return l;
    }
    

    为了防止出错,可以只记住有重复数据时的写法,在无重复数据时也通用!!!

    展开全文
  • 关于lower_bound( )和upper_bound( )的常见用法

    万次阅读 多人点赞 2018-04-30 16:53:16
    lower_bound( )和upper_bound( )都是利用二分查找的方法在一个排好序的数组中进行查找的。在从小到大的排序数组中,lower_bound( begin,end,num):从数组的begin位置到end-1位置二分查找第一个大于或等于num的数字,...

    lower_bound( )和upper_bound( )都是利用二分查找的方法在一个排好序的数组中进行查找的。

    在从小到大的排序数组中,

    lower_bound( begin,end,num):从数组的begin位置到end-1位置二分查找第一个大于或等于num的数字,找到返回该数字的地址,不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。

    upper_bound( begin,end,num):从数组的begin位置到end-1位置二分查找第一个大于num的数字,找到返回该数字的地址,不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。

    在从大到小的排序数组中,重载lower_bound()和upper_bound()

    lower_bound( begin,end,num,greater<type>() ):从数组的begin位置到end-1位置二分查找第一个小于或等于num的数字,找到返回该数字的地址,不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。

    upper_bound( begin,end,num,greater<type>() ):从数组的begin位置到end-1位置二分查找第一个小于num的数字,找到返回该数字的地址,不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。

    #include<bits/stdc++.h>
    using namespace std;
    const int maxn=100000+10;
    const int INF=2*int(1e9)+10;
    #define LL long long
    int cmd(int a,int b){
    	return a>b;
    }
    int main(){
    	int num[6]={1,2,4,7,15,34}; 
    	sort(num,num+6);                           //按从小到大排序 
    	int pos1=lower_bound(num,num+6,7)-num;    //返回数组中第一个大于或等于被查数的值 
    	int pos2=upper_bound(num,num+6,7)-num;    //返回数组中第一个大于被查数的值
    	cout<<pos1<<" "<<num[pos1]<<endl;
    	cout<<pos2<<" "<<num[pos2]<<endl;
    	sort(num,num+6,cmd);                      //按从大到小排序
    	int pos3=lower_bound(num,num+6,7,greater<int>())-num;  //返回数组中第一个小于或等于被查数的值 
    	int pos4=upper_bound(num,num+6,7,greater<int>())-num;  //返回数组中第一个小于被查数的值 
    	cout<<pos3<<" "<<num[pos3]<<endl;
    	cout<<pos4<<" "<<num[pos4]<<endl;
    	return 0;	
    } 


    展开全文
  • STL——upper_bound && lower_bound

    千次阅读 2018-08-18 19:46:19
    lower_bound和upper_bound是C++ STL中提供的函数。操作对象可以是vector、set以及map。 upper_bound(i):返回map中第一个大于key的迭代器指针 lower_bound(i):返回map中第一个大于或等于key的迭代器指针 vector ...

    lower_bound和upper_bound是C++ STL中提供的函数。操作对象可以是vector、set以及map。

    upper_bound(i):返回map中第一个大于key的迭代器指针

    lower_bound(i):返回map中第一个大于或等于key的迭代器指针

    vector

    #include<iostream>
    #include<algorithm>
    #include<vector>
    using namespace std;
    
    int main()
    {
    	int a[]={1,2,4,4,2,1,1,2};
    	
    	vector<int>v(a,a+8);
    	sort(v.begin(),v.end());
    	
    	vector<int>::iterator it1,it2;
    	
    	it1=lower_bound(v.begin(),v.end(),2);
    	it2=upper_bound(v.begin(),v.end(),2);
    	
    	//int x=it1-v.begin();cout<<"x="<<x<<endl;
    	//int y=it2-v.begin();cout<<"y="<<x<<endl;
    	
    	cout<<"Pos_lower->"<<(it1-v.begin())<<endl;
    	cout<<"Pos_upper->"<<(it2-v.begin())<<endl;
    	
    	return 0;
    }
    

    set

    #include<iostream>
    #include<set>
    using namespace std;
    
    int main()
    {
    	set<int>s;
    	set<int>::iterator it1,it2,it;
    	
    	for(int i=1;i<10;++i) s.insert(i);
    	
    	it1=s.lower_bound(3);
    	it2=s.upper_bound(6);
    	
    	cout<<*(it1)<<" "<<*(it2)<<endl;
    	
      	//由于set中没有像vector中那样排序的概念,因此itlow - myset.begin()是错误的
      	
      	s.erase(it1,it2);// 删除区间内的元素,区间左闭右开
      	
      	for(it=s.begin();it!=s.end();++it)
      		cout<<*it<<" ";
      	cout<<endl;
    
      return 0;
    }
    

    map

    #include<bits/stdc++.h>
    using namespace std;
     
    int main ()
    {
    	map<char,int>mp;
    	map<char,int>::iterator it1,it2,it;
    	
    	mp['a']=1;
    	mp['b']=2;
    	mp['c']=3;
    	mp['d']=4;
    	mp['e']=5;
    	
    	it1=mp.lower_bound('b');
    	it2=mp.upper_bound('d');
    	
    	mp.erase(it1,it2);  //区间左闭右开 
    
    	for(it=mp.begin();it!=mp.end();++it)
    		cout<<it->first<<" "<<it->second<<endl;
    
      return 0;
    }
    

     

    展开全文
  • 头文件:lower_bound和upper_bound在头文件algorithm中; 解释:lower_bound和upper_bound为二分法查找元素,其时间复杂度为O(log n)。 一、数组中的lower_bound和upper_bound 对于一个排序数组 nums[5]{1, 2, 5, 7,...

    头文件:lower_bound和upper_bound在头文件algorithm中;
    解释:lower_bound和upper_bound为二分法查找元素,其时间复杂度为O(log n)。

    一、数组中的lower_bound和upper_bound

    对于一个排序数组 nums[5]{1, 2, 5, 7, 9};

    (1) int i = lower_bound(nums, nums + n, val) - nums;

    函数解释:lower_bound函数返回数组 nums 中大于等于 val 的第一个元素的地址,若 nums 中的元素均小于 val 则返回尾后地址。

    #include<iostream>
    #include<algorithm>
    using namespace std;
    
    int main()
    {
    	const int n = 5;
    	int nums[n]{ 1,2,5,7,9 };
    	int i = lower_bound(nums, nums + n, 6) - nums;//大于等于6
    	cout << i << endl;//i=3
    	int j = lower_bound(nums, nums + n, 10) - nums;
    	cout << j << endl;//j=5
    
    	system("pause");
    	return 0;
    }
    

    (2) int i = upper_bound(nums, nums + n, val) - nums;

    函数解释:upper_bound函数返回数组 nums 中大于 val 的第一个元素的地址,若 nums 中的元素均小于等于 val 则返回尾后地址。

    #include<iostream>
    #include<algorithm>
    using namespace std;
    
    int main()
    {
    	const int n = 5;
    	int nums[n]{ 1,2,5,7,9 };
    	int i = upper_bound(nums, nums + n, 6) - nums;//大于6
    	cout << i << endl;//i=3
    	int j = upper_bound(nums, nums + n, 9) - nums;
    	cout << j << endl;//j=5
    
    	system("pause");
    	return 0;
    }
    

    二、STL中的lower_bound和upper_bound

    用法和数组中的用法基本一样,不同之处在于写法和返回值,STL返回值为迭代器,写法如下:

    (1)vector

    #include<iostream>
    #include<algorithm>
    #include<vector>
    using namespace std;
    
    int main()
    {
    	vector<int> vec{ 1,2,5,7,9 };//有序数组
    	vector<int>::iterator it1 = lower_bound(vec.begin(), vec.end(), 9);
    	bool flag1 = it1 == vec.end() - 1;
    	cout << flag1 << endl;//it1指向最后一个元素的迭代器
    	vector<int>::iterator it2 = upper_bound(vec.begin(), vec.end(), 9);
    	bool flag2 = it2 == vec.end();
    	cout << flag2 << endl;//it2为尾后迭代器
    
    	system("pause");
    	return 0;
    }
    

    (2)set

    #include<iostream>
    #include<algorithm>
    #include<set>
    using namespace std;
    
    int main()
    {
    	set<int> s{ 1,2,1,9,7 };//原本就有序
    	set<int>::iterator it1 = s.lower_bound(2);
    	cout << *it1 << endl;//*it1=2
    	set<int>::iterator it2 = s.upper_bound(2);
    	cout << *it2 << endl;//*it2=7
    
    	system("pause");
    	return 0;
    }
    

    (3)map

    #include<iostream>
    #include<algorithm>
    #include<map>
    using namespace std;
    
    int main()
    {
    	map<int, int> m{ {1,2},{2,2},{1,2},{9,2},{7,2} };//有序
    	map<int, int>::iterator it1 = m.lower_bound(2);
    	cout << it1->first << endl;//it1->first=2
    	map<int, int>::iterator it2 = m.upper_bound(2);
    	cout << it2->first << endl;//it2->first=7
    
    	system("pause");
    	return 0;
    }
    
    展开全文
  • lower_bound和upper_bound的用法

    千次阅读 2020-02-02 15:00:01
    二分查找算法可以解决最简单的二分查找问题:a数组单调递增,并且其中...为了解决这些问题,C++ STL提供了两个特别好用的函数:lower_bound()和uppper_bound()。假设a是一个数组,n是数组长度,lower_bound(a, a+n...
  • lower_bound 编辑讨论 本词条缺少概述图,补充相关内容使词条更完整,还能快速升级,赶紧来编辑吧! lower_bound()返回一个 iterator 它指向在[first,last)标记的有序序列中可以插入value,而不会破坏容器顺序的...
  • lower_bound与upper_bound尤其如此( 没事手写了个二分查找,功能用法返回值和STL一毛一样(只是不能传函数,如果是对自己的结构体排序要定义小于运算符QAQ) 然后测试了一下对 intintint 排序,STL耗时是我的我5倍...
  • 在刷力扣上220. 存在重复元素 III的题目遇到了一个问题,原题目如下: 最开始的思路是维护一个最大长度为 k 的滑动窗口,窗口元素放在有序集合中,然后二分查找有序集合... auto p = lower_bound(st.begin(), st.e..
  • ``` #include #include #include ...lower_bound返回一个迭代器,表示第一个小于等于val的元素 upper_bound返回一个迭代器,表示第一个大于val的元素 可是上面代码输出的结果完全不是这回事啊???
  • lower_bound( first , last , value ) 返回指向范围 [first, last) 中首个大于等于 value 的元素的迭代器,若找不到则返回 last 。 降序 upper_bound( first , last , value , greater<type
  • 介绍结构体数组和包含结构体的vector怎么样使用lower_bound进行二分查找,upper_bound同理。 前提: lower_bound:返回数组中第一个大于等于该元素的下标,int aa = lower_bound(array,array+arrayLen,num) - array;...
  • C++中的std::lower_bound()和std::upper_bound()函数

    千次阅读 多人点赞 2020-06-26 23:33:05
    问题是躲不掉的,该来的总会来,这不是代码中又遇到了 `std::upper_bound()` 函数,再来学习一遍好了,在我的印象中每次看到这 `lower_bound` 和 `upper_bound` 两个函数都有些别扭,凡是见到他们必须查一遍,因为我...
  • lower_bound和upper_bound都是用在有序的数组或者容器中的!(以下函数并非是函数原型 只是为了便于说明 可能并不严谨 想看函数原型的请戳这个网址:https://baike.baidu.com/item/lower_bound/8620039?fr=aladdin) ...
  • lower_bound和upper_bound

    2018-04-22 20:04:18
    原创:https://www.cnblogs.com/unknownname/p/8823260.htmllower_bound和upper_boundForwardIter lower_bound(ForwardIter first, ForwardIter last,const _Tp&amp; val)算法返回一个非递减序列[first, last)...
  • lower_bound 和 upper_bound 的用法(利用二分查找的方法在一个排好序的数组中进行查找的) 在从小到大的排序数组中 lower_bound(begin,end,val) 在begin和end中的前闭后开区间进行二分查找,返回大于或等于val的第...
  • 两者都是类似binary-search(二分)...http://stackoverflow.com/questions/31821951/c-difference-between-stdlower-bound-and-stdsetlower-bound 经过测试两者至少在set,int上结果没有区别 如{0,2,4,6}查找3 均返回4
  • lower_bound函数   函数lower_bound()在begin和end中的左闭右开区间进行二分查找,返回大于或等于val的第一个元素位置(迭代器)。如果所有元素都小于val,则返回last的位置。 注意STL中设计区间都是左闭右开,即...
  • lower_bound( )和upper_bound( )都是利用封装的二分查找的方法在一个排好序的数组中进行查找的。 lower_bound (begin,end,num)是将一个排好序的[begin,end)区间中通过二分查找第一个大于等于num的数字,
  • 彻底记住 lower_bound 和 upper_bound 功能和用法

    万次阅读 多人点赞 2018-07-17 20:18:36
    不出所料,在对 4 进行 lower_bound 时,输出结果是 9,因为在升序序列中 lower_bound 返回第一个大于等于 参数val 的 序列值的迭代器,这里 val 为 4,lower_bound 进行二分查找,找到第一个 4 时符合条件所以返回...
  • lower_bound() 函数lower_bound()在**[lo, hi)进行二分查找,返回大于或等于**target的第一个元素的位置。如果所有元素都小于target,则返回hi. private int lower_bound(int[] nums, int lo, int hi, int target) {...
  • 文章目录lower_bound函数和upper_bound函数的用法string中的find函数string中还有rfind()函数 lower_bound函数和upper_bound函数的用法 作用: 用于查找容器中大于等于某值的数,返回的这个数的指针。 vector容器内...
  • } 综合应用 查询某个元素出现的次数 upper_bound - lower_bound #include using namespace std; int a[100005]; int main(){ int n; cin >> n; for(int i=0; i; i++) { cin >> a[i]; } sort(a,a+n); ...
  • lower_bound查找序列中的第一个出现的值大于等于val的位置 int lower_bound(int *array,int l,int r,int targte){ while(l<=r){ int mid=(l+r)/2; if(array[mid]<target)l=mid+1; else r=mid-1; } ...
  • C++中的upper_boundlower_bound比较容易弄混。记住的方法是根据名字记住其功能,如upper_bound表示以某个数为上限,这个数应该放在哪个位置;lower_bound表示以某个数为下限,这个数应该放在哪个位置。同时注意...
  • lower_bound(查找的起始位置,查找的终止为止,需要查找的数 )是返回第一个大于需要查找的数的数的地址 比如,要a[]数组中,从[1,n]中第一个大于s的数的下标 pos=lower_bound(a+1,a+n+1,s)-a; upper_bound(查找的...
  • lower_bound函数实现 函数功能是查找数组中第一个大于等于target的数的位置: int lower_bound(vector<int>& nums, int target) { int l = 0, r = nums.size(); while (l < r) { int mid = l + ...
  • lower_bound()函数使用: 参数: 1、数组元素的地址(起始搜索位置)e.g. a + i; 2、数组元素的地址(末尾搜索位置)e.g. a + n; 3、二分查找的数 返回值:返回第一次大于等于所查找数的地址 (在函数后面减去...
  • int lower_bound(vector<int> &nums, int target) { int l = 0, r = nums.size(), mid; while (l < r) { mid = (l + r) / 2; if (nums[mid] >= target) { r = mid; } else { l = mid + 1; } } ...
  • 首先std::lower_bound()大家都知道,复杂度是o(log n)的,原理是二分查找。但如果用容器std::set加外置的std::lower_bound(),复杂度可不是简简单单的o(log n)的,貌似是o(log n)+n,原因是std::set自带红黑树,结构是...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 87,380
精华内容 34,952
关键字:

*lower_bound