关于二分问题的另一种解法
本文将介绍对于一般「二分」问题的「二进制拆分」解法。
传统解决「二分」问题的方法为找到答案区间的上界和下界，划分 mid 并根据check(mid) 的结果来缩小区间，逼近答案；
而使用「二进制拆分」的方法则不用「显性」地使用区间上下界来逼近答案，不论是从原理上，复杂度分析上，还是从代码上也许都更易理解，本文将详细讲解此方法在各种「二分」问题中的应用。
简述
对于一般的二分问题，总是存在一个 K\tt{K}K，把答案区间分成两个部分，左边为 True\tt{True}True 右边为 False\tt{False}False，反之亦然，我们假设 K\tt{K}K 为左边区间的最后一个值。
假定问题的答案区间为 [1,109][1, 10^9][1,109]，我们有以下代码，求出 K\tt{K}K：
原理
在介绍此方法前，我们需要确定以下事实：
1. 任何正整数都可以拆分成 222 的整数次幂之和；
2. 2n>∑i=0n−12i=2n−1,n∈Z+2^n > \sum_{i=0}^{n - 1}2^i = 2^n - 1, n \in \Z^{+}2n>∑i=0n−1 2i=2n−1,n∈Z+；
3. 对于二分问题的答案区间 [L,R)[L, R)[L,R) 存在 mid∈[L,R)mid \in [L, R)mid∈[L,R) 使得 [L,mid)[L, mid)[L,mid) 区间内的答案满足性质 AAA，[mid,R)[mid, R)[mid,R) 区间内的答案满足性质 BBB，即「区间二分性」。
我们来看比较简单的一种情况，即在长度为 NNN 的有序数组 AAA 中查找第一个大于等于 XXX 的下标。
令最终查询结果的下标为 KKK，那么：
1. 整个数组 [0,K)[0, K)[0,K) 中的所有元素全部小于 XXX，即 Ai<X,0≤i<KA_i \lt X, 0 \le i \lt KAi <X,0≤i<K；
2. 整个数组 [K,N)[K, N)[K,N) 中的所有元素全部大于等于 XXX，即 Ai≥X,K≤i<NA_i \ge X, K \le i \lt NAi ≥X,K≤i<N。
即满足上文中的「区间二分性」。
我们考虑 KKK 的二进制形式，假定 K=53K = 53K=53，其二进制形式为 1101012110101_{2}1101012 ；
由于 2n>∑i=0n−12i=2n−1,n∈Z+2^n > \sum_{i=0}^{n - 1}2^i = 2^n - 1, n \in \Z^{+}2n>∑i=0n−1 2i=2n−1,n∈Z+，所以我们从高位到低位枚举 222 的整数次幂，并令 p←−1p \gets -1p←−1：
1. 对于 252^525，有 p+25=31p + 2^5 = 31p+25=31 落在区间 [0,K)[0, K)[0,K) 中，那么我们令 p←31p \gets 31p←31。
2. 对于 242^424，有 p+24=47p + 2^4 = 47p+24=47 落在区间 [0,K)[0, K)[0,K) 中，那么我么令 p←47p \gets 47p←47。
3. 对于 232^323，有 p+23=55p + 2^3 = 55p+23=55 落在区间 [K,N)[K, N)[K,N) 中，所以我们什么也不做。
4. 对于 222^222，有 p+22=51p + 2^2 = 51p+22=51 落在区间 [0,K)[0, K)[0,K) 中，那么我么令 p←51p \gets 51p←51。
5. 对于 212^121，有 p+21=53p + 2^1 = 53p+21=53 落在区间 [K,N)[K, N)[K,N) 中，所以我们什么也不做。
6. 对于 202^020，有 p+20=52p + 2^0 = 52p+20=52 落在区间 [0,K)[0, K)[0,K) 中，那么我么令 p←52p \gets 52p←52。
最终我们得到了 p=52=K−1p = 52 = K - 1p=52=K−1。
当然具体在执行时，我们要考虑 p+2ip + 2^ip+2i 是否处于数组范围内。
其 CPP\tt{CPP}CPP 代码就像下面这样：
这里 ppp 初始化为 −1-1−1，是因为 222 的整数次幂无法表示 000。
对于 iii 的初始值的取法，假定答案的最小值为 111, 最大值为 MMM，iii 取 ⌊log2M⌋\lfloor \log_2{M} \rfloor⌊log2 M⌋ 即可。
简单来说，不考虑上界太大导致的异常问题，在值域规模不超过 10610^6106 时，iii 可以取 202020；在值域规模不超过 10910^9109 时，iii 可以取 303030，以此类推。
一个小优化
我们可以在初始化与取值时，直接取 222 的整数次幂，从而简化程序。
例子
对于二分查找问题：A8022.查找，我们可以有如下代码解决：
对于二分答案问题：A20952.砍树，我们可以有如下代码解决：
答案区间包含负数
类似于上面提到的 222 的整数次幂无法表示 000 的问题，我们可以转化以下问题，把 ppp 初始化为答案的下界，而在二进制枚举的过程中，我们枚举的值为最终答案与下界的「差」，即可。
答案区间为实数域
对于实数，其可以用二进制近似地表示，所以我们可以更改循环结束的条件和取 2i2^i2i 的方法，使得其在 i<0i \lt 0i<0 时依然正确，从而可以将其应用到实数域上的二分问题。
