二分法剖析

二分二分 折而分之

简单示例 折筷子

比如你有100只筷子 想试试最多一次能折几只

=>折100只:不行
=>折50只:不行
=>折25只:不行
=>折12只:行
=>折18只:行
=>折21只:不行
=>折20只:不行
=>折19只:行
====> 说明你一口气只能折19只
这就是最简单的二分

范围压缩

二分本质其实就是不断压缩取值范围,最终找到定值
用编程逻辑说就是 找到你最"行"区间的最大值

初始范围:[0,100]

=>折100只:不行 [0,99]
=>折50只:不行 [0,49]
=>折25只:不行 [0,24]
=>折12只:行 [12,24]
=>折18只:行 [18,24]
=>折21只:不行 [18,20]
=>折20只:不行 [18,19]
=>折19只:行 [19]

最"行"区间是[0,19] 最大值就是19啦

如何压缩

假设左边范围叫 left ,右边范围叫 right
不行:代表你的能力值低于当前值 所以right要变成当前值-1
行:代表你的能力值高于当前值 left变成当前值+1

=>折100只:不行 [0,99] right->区间中点(50)
=>折50只:不行 [0,49] right->区间中点(25)
=>折25只:不行 [0,24] right->区间中点(12)
=>折12只:行 [12,24] left->区间中点(18)
=>折18只:行 [18,24] left->区间中点(21)
=>折21只:不行 [18,20] right->区间中点(20)
=>折20只:不行 [18,19] right->区间中点(19)
=>折19只:行 [19] right->区间中点(19)

如何确定终值

终值确定其实只看最后一步

所有二分到最后,都会变成 [left,left+1]的格式
为啥捏?很简单 因为每次要不left+1 要不right-1,也就是差值(right和left的差)只有1,如果当前差值为2,那下次变化,差值肯定会变成1

假设现在是倒数第二步:
=>折20只:不行 [18,19] right->区间中点(19)