DAY3-二分查找学习笔记
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
一、二分查找概念
1. 猜数字小游戏
老师心里想了一个 1 到 100 之间的整数，让你来猜。
如果你从 1 开始一个一个猜：
如果答案是 99，就要猜很多次。
更聪明的方法是：
每次都把范围缩小一半，这就是二分查找的想法。
2. 二分核心思想
二分查找的核心思想：
也就是说，我们不用一个一个找，而是不断缩小查找范围。
3. 为什么二分要求有序？
二分查找必须用在“有序”的数据中。
例如从小到大排列：
如果我们查找 9：
* 先看中间的 7
* 9 比 7 大
* 所以 9 一定在右边
但是如果数组没有排序：
看到中间的 3，不能判断 9 一定在左边还是右边。
所以二分查找的前提是：
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
二、普通二分查找
普通二分查找的任务：
如果存在，输出它的位置；如果不存在，说明没有找到。
1. L、R 的含义
我们用两个变量表示当前查找范围：
含义是：
例如：
一开始：
表示从整个数组里找。
2. MID 的计算
中间位置：
也可以写成更安全的形式：
初学时先记住：
3. 三种情况
假设当前中间位置是 mid，我们比较 a[mid] 和 x。
第一种情况：
说明找到了。
第二种情况：
说明中间数太小了，答案如果存在，只可能在右边。
所以：
第三种情况：
说明中间数太大了，答案如果存在，只可能在左边。
所以：
4. 普通二分查找模板
说明：
* 如果输出 -1，表示没有找到。
* 这里的下标从 0 开始。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
三、二分上下界
普通二分只能回答：
但是有时候我们还想知道：
这时候就需要上下界。
1. 为什么需要上下界？
看这个数组：
如果查找 2，普通二分可能找到中间某一个 2，但不一定是第一个 2。
我们有时需要找到：
如果按从 1 开始编号，这个位置就是第 2 个数。
也可能需要找到：
如果按从 1 开始编号，这个位置就是第 5 个数。
这一章我们先不使用 C++ 自带函数，而是学习自己手写。
为了和课堂模板一致，下面的代码使用：
2. 找第一个大于等于 X 的位置
我们要找的是：
例如：
再例如：
3. 左右区域划分
我们想把数组分成两部分：
我们要找的是右边区域的第一个位置。
例如查找第一个 >= 3：
答案是位置 5。
4. 手写模板：找第一个大于等于 X
注意：
* ans 表示目前找到的可能答案。
* 如果最后 ans 还是 -1，表示没有找到大于等于 x 的数。
* 因为要输出答案，所以在完整程序里用 cout << ans << endl;。
5. 边界怎么移动？
当：
说明 mid 这个位置符合要求，它可能就是答案。
但是我们要找的是“第一个”符合要求的位置，所以还要继续往左找。
所以：
当：
说明 mid 太小了，不可能是答案，答案只能在右边。
所以：
6. 不存在的情况
例如：
没有任何数 >= 10。
这时 ans 一直不会被修改，最后还是：
7. 找第一个大于 X 的位置
现在我们换一个问题：
例如：
8. 左右区域划分
我们想把数组分成两部分：
我们要找的是右边区域的第一个位置。
例如查找第一个 > 2：
答案是位置 5。
9. 手写模板：找第一个大于 X
10. 边界怎么移动？
当：
说明 mid 这个位置符合要求，它可能就是答案。
但是我们要找的是“第一个”符合要求的位置，所以继续往左找。
所以：
当：
说明 mid 不够大，不可能是答案，答案只能在右边。
所以：
11. 两种上下界区别总结
要找什么 判断条件 找到后怎么做 不符合时怎么做 第一个 >= x a[mid] >= x ans = mid; r = mid - 1; l = mid + 1; 第一个 > x a[mid] > x ans = mid; r = mid - 1; l = mid + 1;
最重要的区别：
12. 课堂记忆方法
这两个模板长得几乎一样，只差一个判断条件：
或者：
其他部分都可以先照着同一个模板写。
完整记忆：
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
四、STL 二分函数
C++ 已经帮我们写好了二分查找函数。
使用前需要：
1. LOWER_BOUND()
格式：
含义：
2. UPPER_BOUND()
格式：
含义：
3. 返回值转换成下标
STL 的 lower_bound() 和 upper_bound() 返回的不是普通整数下标，而是一个“位置指针”。
要转换成下标，可以这样写：
或者：
4 查找第一个 >= X 的位置
5 查找第一个 > X 的位置
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
五、二分查找易错点
1. 忘记数组必须有序
错误想法：
正确想法：
如果题目没有保证有序，可能需要先排序：
2. L、R 的范围写错
普通二分常用：
上下界二分常用：
不要把两个模板混在一起乱改。
3. MID 写错
推荐写法：
4. 更新边界时漏掉 1
普通二分中：
因为 mid 已经检查过了。
上下界二分中：
因为 mid 有时可能就是答案，不能随便丢掉。
5. 忘记判断 POS == N + 1
例如：
如果 pos == n + 1，说明没有找到符合条件的位置。
不能直接访问：
否则会访问到数组外面。
6. 下标从 0 开始还是从 1 开始
C++ 普通数组的下标一般从 0 开始。
如果题目要求输出第几个数，可能要输出：
如果题目要求输出下标，通常输出：
读题时一定要看清楚。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
六、二分综合应用总结
1. 常见问题和方法
问题 方法 查找 x 是否存在 普通二分 找第一个 >= x lower_bound 找第一个 > x upper_bound 统计 x 出现次数 upper_bound(x) - lower_bound(x) 统计 [x, y] 中数量 upper_bound(y) - lower_bound(x)
2. 记忆口诀
3. 推荐背诵模板
普通二分：
第一个 >= x：
第一个 > x：
统计 x 的个数：
统计 [x, y] 的个数：
1. 二分查找必须用在有序数组中。
2. lower_bound 找第一个 >= x 的位置。
3. upper_bound 找第一个 > x 的位置。
