<1>lower_bound

(1).

上述代码返回在升序排序的序列a中第一个大于等于 t 的元素的地址.

示例:

(2)

上述代码返回在升序排序的序列a中第一个大于等于 t 的元素的下标.

示例:

例题:

P2249 【深基13.例1】查找

P2249 【深基13.例1】查找 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

题目描述

输入 n 个不超过 1e9 的单调不减的（就是后面的数字不小于前面的数字）非负整数 a1,a2,…,an，然后进行 m 次询问。对于每次询问，给出一个整数 q，要求输出这个数字在序列中第一次出现的编号，如果没有找到的话输出 −1 。

输入格式

第一行 2 个整数 n 和 m，表示数字个数和询问次数。

第二行 n 个整数，表示这些待查询的数字。

第三行 m 个整数，表示询问这些数字的编号，从 1 开始编号。

输出格式

输出一行，m 个整数，以空格隔开，表示答案。

输入输出样例

输入

11 3
1 3 3 3 5 7 9 11 13 15 15
1 3 6

输出

1 2 -1

说明/提示

数据保证，1≤n≤1e6，0≤ai,q≤1e9，1≤m≤1e5

AC Code:

<2>upper_bound

(1)

上述代码返回在升序排序的序列a中第一个大于 t 的元素的地址.

示例:

(2)

上述代码返回在升序排序的序列a中第一个大于 t 的元素的下标.

例题:

最大的数II

题目描述

今天，羊村要举行一次“知识竞赛”，很多羊都去参加了，村长见羊太多，决定先举行预选，选出一些人，再参加比赛，给出一个正整数M，求S=1+2+3+…+N的值中，符合条件S<=M的最大的N的值。如给出M的值为7，则N为3，因为1+2+3=6，1+2+3+4=10，所以符合S<=M的条件下，N的最大值为3。对于给定的M的值，喜羊羊很快就说出了符合条件的N的值。现在请你编写一个解决这个问题的程序。

输入

只有一个数，就是M的值。（M<=1000000000）

输出

只有一个数，就是符合题目条件的N的最大值。

样例输入

样例输出

思路: