upper_bound

一句话理解

upper_bound 找第一个大于 x 的位置。

为什么要学

配合 lower_bound 可以数有多少个 x。

讲解

个数 = upper_bound - lower_bound。

同样要求有序。

例子

int a[5] = {1, 3, 3, 7, 9};
cout << (upper_bound(a, a + 5, 3) - a);

输出：

3

第一个 >3 的是 7，下标 3。于是 3 出现在 [1,3)。

常见错误

• 和 lower_bound 记反。
• 用它找 <=x 却没减 1。