好的我又来当黑奴码我的笔记力
求赞！！！
@忘川秋裤团长帮帮我吧
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
正文:
一，二分查找(或称"折半查找")
1，定义：在一组有序的数组中查找一个元素的一种效率较高的查找方法
例子引入：”在1-100里查找一个指定数m
暴力查找：从1到100依次枚举，但效率太低
有没有更好的查找方法呢？有的兄弟，有的
先猜50，得知是等于它、比它大还是比它小
如果相等，就结束；如果比它大，则问75；如果比它小，则问25。以此类推。
向上面这种方法就叫二分查找“
2，步骤
(1),升序排列序列(1-n)
(2),将中间值mid与目标x比较
①，mid = x,结束
②，mid > x,范围缩小至前一半(即：右区间移动到mid-1)
③，mid < x,范围缩小至后一半(即：左区间移动到mid+1)
(3),重复步骤(2),直至找到(或全部排除)
3,次数：log(2,n) + 1
4，时间复杂度：O(logn)
相当于在100内找n最多只需7次，因为6 < log(2,100) < 7，然后向上取整得7
5，模板代码：
或
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
二，二分上下界
1，二分下界
(1),定义：在一个非降序列(可上升可不变)里查找>=x的第一个位置
(2),查找情况：
①，x存在，返回x首次出现位置
②，x不存在，返回首个大于等于x出现的位置
③，都比x小，返回n+1(即：x只有放在最后面才能保持这个序列是非降序列)
(综上，找出首个大于等于x的位置，不存在则返回n+1)
(3),步骤：
①，按非降序排序
②，将中间值mid与目标元素x比较
I,mid >= x：存储此位置，向左区间寻找，更新r为mid-1
II,mid < x：向右区间寻找，更新l为mid-1
③返回答案
(4),时间复杂度：O(logn)
(5),模板代码：
2，二分上界
(1)，定义：在一个非降序列中查找首个>x的位置
(2)，查找情况：
①，x存在，返回大于x的首个位置
②，均小于等于x，返回n+1(即：x只有放在最后面才能保持这个序列是非降序列)
(综上，查找首个大于x的位置，无则返回n+1)
(3),步骤：
①，按非降序排序
②，将中间值mid与目标元素x比较
I,mid > x：存储此位置，向左区间寻找，更新r为mid-1
II,mid <= x：向右区间寻找，更新l为mid-1
③返回答案
(4)时间复杂度：O(logn)
(5),模板代码：
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
三，STL二分算法
1，头文件：algorithm
2,函数：(数组下标从1开始)
(1)，下界：lower_bound(数组名 + 1，数组名+数组长度+1，查找元素) - 数组名；
(2)，上界：upper_bound(数组名 + 1，数组名 + 数组长度 + 1，查找元素) - 数组名；
注意：上界-下界 = 元素出现次数
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
四，二分答案
1，二分答案求上界
(1),问题：要求答案足够大
(2),模板代码：
2，二分答案求下界
(1),问题：要求答案尽量小
(2),模板代码：
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
五，例题
题单放我团队里了，各位大佬有兴趣的可以加我团队看
二分题单
来道例题：
T44263.保龄球
本题考察二分查找，由于不同位置有不同的瓶子数，需要用结构体将瓶子数绑定
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
以上就是本期笔记内容了，各位大佬点个赞吧
@AC君 555求看
