lower_bound 和 upper_bound 用于在有序序列（如数组或容器）中进行二分查找。

lower_bound 函数用于查找在有序序列中第一个大于或等于给定值的元素的位置。

upper_bound 函数用于查找在有序序列中第一个大于给定值的元素的位置。

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

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

这两个函数在查找失败时返回的是一个迭代器，该迭代器指向有序序列中第一个大于给定值的位置。如果查找成功，则返回的迭代器指向找到的元素。

// 爱码岛编程
#include <bits/stdc++.h>
using namespace std;

int main() {

    // 数组
	int n = 8;
	int arr[] = {1, 4, 5, 7, 8, 9, 11, 13};
	
	int* lb = lower_bound(arr, arr + n, 7); // 大于等于7的元素的位置
	cout << lb - arr << endl; // 3
	
	int* ub = upper_bound(arr, arr + n, 7); // 大于7的元素的位置
	cout << ub - arr << endl; // 4

    return 0;
}

最右

可以借助 upper_bound 函数查找在有序序列中小于给定值的元素最右位置。

// { 1, 4, 5, 7, 8, 9, 11, 13 }
int findRight(int arr[], int n, int target) {    // target = 7
    int *ub = upper_bound(arr, arr + n, target); // 大于7的元素的位置（8的位置）
    if (ub == arr) {
        return -1;
    }
    --ub; // 小于等于的位置
    
    while (*ub == target) { // 去掉等于的，就是小于的
        --ub;
        if (ub < arr) {
            return -1;
        }
    }
    return ub - arr;
}