• 自定义 lower_bound 和 upper_bound

#include <bits/stdc++.h>
using namespace std;

/*
自定义比较函数都是实现"<"运算符操作；lower_bound找左边界（下限），遍历元素在左（下）；upper_bound找右边界（上限），被遍历元素在右（上）。

根据以上原则我们可以猜测到lower_bound和upper_bound的各自终止条件：

lower_bound()在比较函数（记为cmp）返回false时终止查找（找到前cmp返回true）。
upper_bound()在比较函数（记为cmp）返回true时终止查找（找到前cmp返回false）
————————————————
版权声明：本文为CSDN博主「智能汽车人」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/Janeiskangs/article/details/139902854
*/

struct Elem {
	int val = 0;
	Elem(int val): val(val) {}
};

// 自定义比较函数，目标是实现<操作，
// lower_bound找下边界（左），elem在下（左）
bool LowerCompare(Elem elem, int target) {
	return elem.val < target; //实现<
}

// upper_bound找上边界（右），elem在上（右）
bool UpperCompare(int target, Elem elem) {
	return target < elem.val; //实现<
}

int main() {
	std::vector<Elem> vec = {1, 2, 4, 4, 4, 6, 7};
	int target = 4;
	
	// 使用自定义比较函数进行 lower_bound 查找
	auto lower = std::lower_bound(vec.begin(), vec.end(), target, [&](Elem elem, int target) {
		return elem.val < target;
	});
	
//	auto lower = std::lower_bound(vec.begin(), vec.end(), target, LowerCompare);
	
	if (lower != vec.end()) {
		int lowerIndex = lower - vec.begin();
		cout << "Lower bound of " << target << " is at index: " << lowerIndex << " with value: " << lower->val << '\n';
	} else {
		cout << "Lower bound of " << target << " not found!" << std::endl;
	}
	
	// 使用自定义比较函数进行 upper_bound 查找
	auto upper = std::upper_bound(vec.begin(), vec.end(), target, [&](int target, Elem elem) {
		return target < elem.val;
	});
	
//	auto upper = std::upper_bound(vec.begin(), vec.end(), target, UpperCompare);
	
	if (upper != vec.end()) {
		int upperIndex = upper - vec.begin();
		cout << "Upper bound of " << target << " is at index: " << upperIndex << " with value: " << upper->val << '\n';
	} else {
		cout << "Upper bound of " << target << " not found!" << std::endl;
	}
	
	return 0;
}