“二分” 备忘

一直对二分查找的实现有些许恐惧，不想去考虑各种边界情况
不知为何今天突然想通了，给自己一个记录吧
从这道题入手： 数的范围

mid的生成

我们都知道mid是通过l+r除以二得到，但为何有时需要加上1，有时又不加上1
理由是： 有时需要得到大于等于它的最小，有时需要得到小于等于它的最大
例子，考虑a = [0, 1, 2, 3], l = 0, r = len - 1 = 3
1当mid = l + r >> 1时，mid = 1，在序列中属于中间靠左的那个元素
2当mid = l + r + 1 >> 1时，mid = 2，在序列中属于中间靠左的那个元素

当序列个数为奇数时，两种方式选取的mid相同，因此我们考虑序列个数为偶数时的情况即可

l和r的赋值

mid生成后，就需要将搜索元素x与a[mid]进行比较了
1如果想要得到大于等于x的最小（第一个大于等于x），就需要：if(x <= a[mid]) r = mid; else l = mid + 1;
2如果想要的到小于等于x的最大（第一个小于等于x），就需要：if(a[mid] <= x) l = mid; else r = mid - 1;

这样讲两者对比着看应该就能理解了
为了防止我之后还是不理解，解释如下：
1. 此时由于mid在中间靠左的元素上，x <= a[mid]时，就表示x在mid（包含mid）的元素左侧，r置为mid；否则l置为mid+1（因为此时可以把mid排除出去了）
2. 此时由于mid在中间靠右的元素上，a[mid] <= x时，表示x在mid（包含mid）的元素右侧，l置为mid；否则r置为mid-1