算法学习步骤

• 严禁照着老师的代码编写完成
• 只给思路不给实现，学生需要逐步培养运用思路就能完成题目的能力。

二分常用函数

• lower_bound() ：二分找到刚好 大于或等于 给定数字的下标，不存在返回数组最后一个元素的下一个位置，一般是 $n+1$。

lower_bound(查找的起始元素地址，查找的末尾元素的下一个地址，带查找元素 x) - 数组地址

使用前提：保证数组从小到大排序。

示例：

sort(a + 1, a + n + 1);
int pos = lower_bound(a + 1, a + n + 1, x) - a; // 注意最后减 a

• upper_bound() ：二分找到刚好 大于 给定数字的下标，不存在返回数组最后一个元素的下一个位置，一般是 $n+1$

upper_bound(查找的起始元素地址，查找的末尾元素的下一个地址，带查找元素 x) - 数组地址

使用前提：保证数组从小到大排序。

示例：

sort(a + 1, a + n + 1);
int pos = upper_bound(a + 1, a + n + 1, x) - a; // 注意最后减 a

常见应用

• 使用 lower_bound() 可以找到数组中从左往右 最靠左 且等于 $x$ 的位置。

int pos = lower_bound(a + 1, a + n + 1, x) - a; // 注意最后减 a
if (a[pos] == x) cout << pos;
else cout << -1; // 不等于说明不存在 x

• 使用 upper_bound() 可以找到数组中从左往右 最靠右 且等于 $x$ 的位置。

解释：pos 这个位置的左边有可能就是最后一次等于 $x$ 的，判断 a[pos - 1] 和 $x$ 的关系即可。

int pos = upper_bound(a + 1, a + n + 1, x) - a; // 注意最后减 a
if (a[pos - 1] == x) cout << pos;
else cout << -1; // 不等于说明不存在 x