关于二分的选择

学算法以来，就一直总把两种二分弄混，写这篇博客来记录一下怎么区分二者

二分的分类

按照y总的算法基础课，二分主要有两类

1. 左加右不二分不
   完整代码如下

while (l < r)
{
    int mid = l + r >> 1;
    if (check(mid)) r = mid;    // check()判断mid是否满足性质
    else l = mid + 1;
}

1. 左不右减区间加
   完整代码如下

while (l < r)
{
       int mid = l + r + 1 >> 1;
       if (check(mid)) l = mid;
       else r = mid - 1;
}

以上两种代码最后分出来的边界值应该是l或者r都行（毕竟分出来后l和r必定相等）

算法的具体案例

对于第一种方法

按照单步跟踪算法的实现，我们可以看出，当以第一种二分算法，以a[x]>=3为要求来对数组a[7]={0,1,2,3,4,5,6}进行二分的时候，最后得到的结果是3，但是将条件换成a[x]<3时，得到的结果是6

由此分析我们可以得到，第一种二分使用的约束条件在最后分出来后应该是满足后半段的，而且二分出来的结果是从前往后数一个满足要求的元素的下标

对于第二种方法

同样以a[x]>=3为要求来对数组a[7]={0,1,2,3,4,5,6}进行第二种二分的时候，最后得到的结果却是6，但是将条件换成a[x]<3时，得到的结果是2

由此分析我们可以得到，第二种二分使用的约束条件在最后分出来后应该是满足前半段，而且二分出来的结果是从前往后数最后一个满足要求的元素的下标

总结

两种二分用于不同的情况
第一种用于找第一个符合条件的
第二种适合找最后一个符合条件的

所以下面编一段顺口溜帮助记忆：

左加右不二分不，前无古人后来者
左不右减区间加，末代既成后无人