方法一:
假设有一个总区间,经由我们的 check 函数判断后,可分成两部分,
这边以o作 true,.....作 false 示意较好识别
如果我们的目标是下面这个v,那麽就必须使用模板 1: r = mid
................vooooooooo
假设经由 check 划分后,整个区间的属性与目标v如下,则我们必须使用模板 2: l = mid
oooooooov...................
方法二:通过取余(或最值)来判断
划分区间直至最后区间还剩两个元素时,有两种情况
用模板一来解释 假设check函数是
while(l < r){
int mid = l + r >> 1;
if(q[mid] >= x) r = mid;
else l = mid + 1;
}
①:[false,true] 这种情况会通常会因为不满足check 而进入else
如[1,2] 1+2 >> 1 = 1 不满足等于2的结果 所以 l = mid + 1; 答案就为2
②:[true,true] 这种情况就需要通过取余判断
eg : [2,3] 如果是向上取余结果会为 2+3 >> 1 = 3 会进入死循环
向下取余 2+3 >> 1 = 2 此时就可求出答案为2
模板二的情况也可以以此类推
所以一个大致的结论就是:
如果取的是最小值的话,向下取余,用模板1
取的是最大值的话,向上取余,用模板2
结合方法一来看就是:................vooooooooo (小到大排列) 出现这种情况时特判[v,o]
需要取v, 向下取余,所以是模板1
oooooooov................... 出现这种情况时特判[o,v]
取v, 向上取余,所以是模板2