当前位置： 首页 > news >正文

lower_bound和upper_bound详解

news 来源：原创 2024/4/27 19:41:25

lower_bound和upper_bound详解

函数作用

可以对有序连续的空间进行二分查找。
lower_bound默认查找大于等于某值所在连续空间的位置。
upper_bound默认查找大于某值所在连续空间的位置。
一般连续空间就是数组或者STL中的vector

库函数定义

template<typename _ForwardIterator, typename _Tp, typename _Compare>
    inline _ForwardIterator
    lower_bound(_ForwardIterator __first, _ForwardIterator __last,
		const _Tp& __val, _Compare __comp);

template<typename _ForwardIterator, typename _Tp>
    inline _ForwardIterator
    lower_bound(_ForwardIterator __first, _ForwardIterator __last,
		const _Tp& __val);

/*--------------------------------------------------*/
/*--------------------------------------------------*/

template<typename _ForwardIterator, typename _Tp, typename _Compare>
    inline _ForwardIterator
    upper_bound(_ForwardIterator __first, _ForwardIterator __last,
		const _Tp& __val, _Compare __comp);

template<typename _ForwardIterator, typename _Tp>
    inline _ForwardIterator
    upper_bound(_ForwardIterator __first, _ForwardIterator __last,
		const _Tp& __val);

上面是两个函数的声明， 其中注意重载中有一个类模板可以提供比较函数。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-CjbaQ3do-1680014417298)(C:\Users\hp\AppData\Roaming\Typora\typora-user-images\image-20230328214428829.png)]

返回值是返回迭代器。

代码运用

void Func1() {
	std::vector<int> vec{ 1,3,5,7,9 };
	auto iter=std::lower_bound(vec.begin(), vec.end(), 3);
	std::cout << iter - vec.begin() << " " << (*iter) << std::endl;
	std::cout << vec.end() - vec.begin() << std::endl;
	auto iter2 = std::upper_bound(vec.begin(), vec.end(), 3);
	std::cout << iter2 - vec.begin() << " " << *iter2 << std::endl;
}

输出结果:

1 3
5
2 5

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-blxcRXwX-1680014417300)(C:\Users\hp\AppData\Roaming\Typora\typora-user-images\image-20230328214935558.png)]

提升运用

在平时比较时，常用到less(小到大排序)与greater(大到小排序)，它们重载()运算符使得两个值可以进行比较， 在使用lower_bound或upper_bound时也常常用到。

/// One of the @link comparison_functors comparison functors@endlink.
  template<typename _Tp>
    struct greater : public binary_function<_Tp, _Tp, bool>
    {
      _GLIBCXX14_CONSTEXPR
      bool
      operator()(const _Tp& __x, const _Tp& __y) const
      { return __x > __y; }
    };

  /// One of the @link comparison_functors comparison functors@endlink.
  template<typename _Tp>
    struct less : public binary_function<_Tp, _Tp, bool>
    {
      _GLIBCXX14_CONSTEXPR
      bool
      operator()(const _Tp& __x, const _Tp& __y) const
      { return __x < __y; }
    };

对于自定义类型也是可以自己重载<, >符号达到比较的效果。

使用less或greater

void Func2() {
	std::vector<int> vec = { 2,4,6,8,10 };
	auto iter1 = std::lower_bound(vec.begin(), vec.end(), 4, std::less<int>());
	std::cout << iter1 - vec.begin() << " " << *iter1 << std::endl;
	auto iter2 = std::upper_bound(vec.begin(), vec.end(), 4, std::less<int>());
	std::cout << iter2 - vec.begin() << " " << *iter2 << std::endl;
	auto iter3 = std::lower_bound(vec.begin(), vec.end(), 4, std::greater<int>());
	if (iter3==vec.end()) {
		/*return;*/这里找不到
	}
	//std::cout << iter3 - vec.begin() << " " << *iter3 << std::endl;
	
    //大到小排序
	std::vector<int> vec2 = { 5,4,3,2,1 };
	auto iter4 = std::lower_bound(vec2.begin(), vec2.end(), 2, std::greater<int>());
	std::cout << iter4 - vec2.begin() << " " << *iter4 << std::endl; //iter4-vec2.begin()得到的是该地址的下标

}

1 4
2 6
3 2

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-5W2FGcne-1680014417300)(C:\Users\hp\AppData\Roaming\Typora\typora-user-images\image-20230328220253481.png)]

总结

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

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

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

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

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

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

首先，大家都说用这两个函数之前必须是在有序的数组中，但是都没有说明为什么是在有序的数组，因为他们的底层实现是二分查找（这个也是我在别人的题解的时候知道的）我们先来看lower_bound(后有lower_bound的底层实现，更容易理解lower_bound的原理）

template <class ForwardIterator, class T>
ForwardIterator lower_bound (ForwardIterator first, ForwardIterator last,  const T& val);


template <class ForwardIterator, class T, class Compare>
ForwardIterator lower_bound (ForwardIterator first, ForwardIterator last, const T& val, Compare comp);
模板参数解释：
  1. ForwardIterator就是一个迭代器，vector< int > v，v数组的首元素就是 v.begin()
  2. T&val , 就是一个T类型的变量
  3. Compare 就是一个比较器，可以传仿函数对象，也可以传函数指针。

函数作用：

前提是有序的情况下，lower_bound返回指向第一个值不小于val的位置，也就是返回第一个大于等于val值的位置。（通过二分查找）

参数、返回值含义：

  1. first,last: 迭代器在排序序列的起始位置和终止位置，使用的范围是[first,last).包括first到last位置中的所有元素。
  2. val: 在[first,last)下，也就是区分（找到大于等于val值的位置，返回其迭代器）。
  3. comp： 主要针对于原型二，传一个函数对象，或者函数指针，按照它的方式来比较。
  4. 返回值：返回一个迭代器，指向第一个大于等于val的位置。

原型2的第四个参数（比较器）可以用来排序，再来获取大于等于val值的迭代器。

void Func4() {
	class Student {
public:
		int id;
		std::string name;
		
		Student(int id_,std::string name_)
			:id(id_)
			,name(name_)
		{}
	};
	
	std::vector<Student> vec{ {1,"苹果"},{2,"香蕉"},{3,"梨子"} };
	auto iter = std::lower_bound(vec.begin(), vec.end(), Student(0, "西瓜"), [](const Student& s1, const Student& s2)->bool {
		return s1.id < s2.id;
		});
	std::cout << iter - vec.begin() << " " << (*iter).id<<" "<<(*iter).name << std::endl;
}

输出结果:

0 1 苹果

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-LlEhRzgt-1680014417301)(C:\Users\hp\AppData\Roaming\Typora\typora-user-images\image-20230328223150019.png)]

类重载()就是函数对象或者仿函数。

struct CompareV
{
	bool operator() (const Stu& s1,  const Stu& s2)//  排名升序
	{	
		return s1._num < s2._num;
	}
};
lower_bound的底层实现
int lower_bound(vector<int>& nums, int x) {
	int left = 0;
	int right = nums.size() - 1;

	while (left <= right) {
		int mid = left +(right - left) / 2;
		if (x > nums[mid]) {
			left = mid + 1;
		}
		else {
			right = mid - 1;	
		}
	}
	return left;
}
upper_bound的底层实现

用法和上面类似。只是把lower_bound的大于等于换成大于。仿函数等等全是相同的用法

int upper_bound(vector<int>& nums, int x) {
	int left = 0;
	int right = nums.size() - 1;

	while (left <= right) {
		int mid = left +(right - left) / 2;
		if (x >= nums[mid]) {       //这里是大于等于
			left = mid + 1;
		}
		else {
			right = mid - 1;	
		}
	}
	return left;
}

题目运用

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。请必须使用时间复杂度为 O(log n) 的算法。

lower_bound()的返回值是第一个大于等于 target 的值的地址，用这个地址减去first，得到的就是第一个大于等于target的值的下标。

在数组中：

int n = lower_bound(a , a + x , target) - a;//x 为数组的长度

在vector中：

int n=std::lower_bound(vec.begin(),vec.end(),target)-vec.begin()

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
      return lower_bound(nums.begin(),nums.end(),target)-nums.begin();
}
};

普通方法,二分:

int l = 0,r = nums.size() - 1;
       while(l <= r)
       {
           int mid = l +( (r-l) >> 1);
           if(nums[mid] == target)
             return mid;
             else if(nums[mid] > target)
                 r = mid-1;
                 else if(nums[mid] < target)
                 l = mid + 1;
       }
       return l;

相关文章：

  • 【软件测试】基础知识第一篇
  • Win10安装Nginx
  • Java并发之AQS原理
  • Chat GPTAPI对接-gpt装什么window系统
  • 基于springboot实现大学生租房系统演示【附项目源码】
  • 【C++笔试强训】第八天
  • Linux中 ps命令详解
  • 为什么努力学模电依然学不好的原因？
  • 【NLP经典论文阅读】Efficient Estimation of Word Representations in Vector Space（附代码）
  • Ubuntu系统设置
  • 迪赛智慧数——柱状图（正负条形图）：“光棍”排行榜TOP10省份
  • DiskGenius功能强大的磁盘管理工具可以恢复硬盘被删除的数据吗？
  • TongWeb上传文件功能介绍
  • 实验4 Matplotlib数据可视化
  • 量子运算-比算子描述更广泛的一类刻画量子态在客观世界演化的数学工具
  • 应急响应/入侵排查
  • Parasoft帮助中移智行顺利获得A-SPICE L3和ISO26262功能安全认证证书
  • 2023年泰迪杯数据挖掘挑战赛B题--产品订单数据分析与需求预测（数据处理）
  • ChatGPT使用案例之画思维导图
  • Xilinx JESD204B IP使用