二分算法

二分的本质不是单调性。
（有单调性一定可以二分，但是二分可以做的题，不一定需要满足单调性。）
二分的本质是二段性
就是有一个分界点，分界点左边都是状态x，分界点右边都是状态y。

通过二分就可以找到红色区域的右边界值或者绿色区域的左边界值

当想找不满足性质的边界值（红色区域的右边界值）
即：将区间[l, r]划分成[l, mid]和[mid + 1, r]。

1. 找中间值 /(mid =/frac{l+r}{2}/)
2. if(check(mid))等于true或者是false
   check(m)是检查m是在满足红颜色区间的性质（检查是不是在红色区间）

• • 如果是true 正确区间：/([l，mid]/) ==> /(r=mid/)
• • 如果是false 正确区间：/([mid+1,r]/) ==> /(l=mid+1/)

当想找满足性质的边界值（绿色区域的左边界值）
即：将区间[l, r]划分成[l, mid – 1]和[mid, r]。

1. 找中间值 /(mid =/frac{l+r+1}{2}/)
   计算mid时需要加1

2. if(check(mid))等于true或者是false
   check(m)是检查m是在满足绿颜色区间的性质（检查是不是在绿色区间）

• • 如果是true 正确区间：/([mid,r]/) ==> /(l=mid/)
• • 如果是false 正确区间：/([l,mid-1]/) ==> /(r=mid-1/)