..
二分
7月14号老师布置任务让15号讲二分
7月15号返校听填报志愿指导没讲成
7月16号组织了场内部比赛又没讲成
7月17号最后又安排我讲的归并排序
哈哈哈哈哈哈哈哈。。。。。。。。
引入
提到二分，大多数oier的第一反应应该是二分查找，即在一个有序序列中查找一个数字或字符是否出现及某次出现的位置。
而正因为序列是有序的，所以在学习此算法时通常会误认为二分的本质是在具有单调性的序列上进行定位操作。
实则不然……
二分的本质
寻找不同性质区间的边界。
二分的本质实际上是根据某一性质将某一序列划分为前后两部分，并寻找这两部分的边界。
如之前提到的二分查找，在长度为 $N$ 的序列 a 中查找数字 x 首次出现的位置，实际上是将序列划分为 a[i] < x 和 a[i] >= x 左右两部分，并寻找 a[i] >= x 区间的左边界。
至于判断数字 x 是否存在于序列 a 中，则可根据二分得到的边界值进行判断，即判断 a[i] == x。
模版
这里粘两个 yxc 的二分模版
// 区间[l, r]被划分成[l, mid]和[mid + 1, r]时使用：
int bsearch_1(int l, int r)
{
while (l < r)
{
int mid = l + r >> 1;
if (check(mid)) r = mid;
else l = mid + 1;
}
return l;
}
// 区间[l, r]被划分成[l, mid - 1]和[mid, r]时使用：
int bsearch_2(int l, int r)
{
while (l < r)
{
int mid = l + r + 1 >> 1;
if (check(mid)) l = mid;
else r = mid - 1;
}
return l;
}
讲一下第二个板子为什么 mid = l + r + 1 >> 1 要 + 1 。
当 l 与 r 差值为 1 时，mid = l + r + 1 >> 1 后 l 值与 mid 相同。此后若 check(mid) 返回值为 true，l 的值仍与 mid 相同，这将进入一个死循环而导致 RE 。故需要 + 1 使得写入 mid 的值为 r 。
至于什么情况下需要 + 1 ，请自行理解并视情况而定。
习题及代码
STO yxc OTZ