C++数组中lower_bound和upper_bound函数的用法

lower_bound 函数

首先，对于一个升序的数组（下标从 0 或者 1 开始是无所谓的，这里假设下标从 1 到 n），即：

a[1] <= a[2] <= a[3] <= ... <= a[n]

这个数列是（非严格）单调递增的。

lower_bound(a+1, a+n+1, x)

会返回 a[1..n] 中所有 \(\ge x\) 的元素里面最小的那个数的地址。

也就是说，如果 \(a[p-1] \lt x \le a[p] \le a[p+1] \le ...\) ，则 lower_bound 函数会返回 \(a[p]\) 的地址。

因为 \(a[p]\) 的地址可以表示为 \(a+p\)，而 \(a\) （\(a = a + 0\)）表示的是 \(a[0]\) 的地址，所以

int p = lower_bound(a+1, a+n+1, x) - a;

就能够获得 \(a[p]\) 的下标 \(p\) 了。\(p\) 对应的是所有 \(\ge x\) 的元素的下标的最小值。

也就是说：此时下标 \(p\) 对应的 \(a[p]\) 是最靠前的 \(\ge x\) 的那个数。

特殊地，如果 a[1..n] 范围内的所有数都 \(\lt x\)，则 \(p\) 对应 \(n+1\)（查找的范围是 \(a[1..n]\) 后一个位置的数）。

upper_bound函数

• lower_bound：\(\ge x\)
• upper_bound：\(\gt x\)

即：

int p = upper_bound(a+1, a+n+1, x) - a;

则 p 对应的是 a[1..n] 中所有 \(\gt x\) 的元素的下标的最小值。