前置知识：

1. 一个大于1的整数，如果不停除以2，那么结果一定先到1，再到0.
   为什么？给一个2进制的解释：一个正整数的最高位一定是1，除以2相当于右移1位，那么移动到只剩最高位的时候，就是1了。
2. 奇数个数字有唯一一个中位数，但偶数个数字却有2个中位数，类似1 2 3 4，有中位数2 3,而c++中整除取到的是左边的中位数2，(0+3)/2=1称之为”下取整“，如果要想取到3,可以(0+3+1)/2=2,称为”上取整“。

2分思路

1. 二分的本质：如果再区间能找到一种性质，把整个区间一分为二，一半满足，一半不满足，二分就可以找到边界。
2. 二分是通过不断缩小区间，使整个区间缩小到只有1个数，这时左边界、有边界、中点重合了，也就找到了。
3. 只要不是空区间，二分总可以找到一个边界，所以二分肯定有解的，只看这个解符合题目的要求吗？
4. 为什么会有不同的分法？因为我们要确保要找的答案，会落在边界上，这样通过2分找到边界，也就找到答案。
   看图：
   二分定义：

关于789题的图解：

习题

acwing 68. 0到n-1中缺失的数字
acwing 896 最长上升子序列2

二分如何少出错

1、范围永远左闭右开，当满足不了条件时，最后会落在末尾的下一个位置，也就是右开的位置。
2、条件永远选“大于等于”和“大于”两种，和stl的lower_bound和upper_bound保持一致。