二分

定义

二分查找，也称折半搜索、对数搜索，是用来在一个有序序列中查找某一元素的算法。

理解

使用二分法的前提条件是有序，如果序列无序或者函数不单调，那么二分也就无从谈起。
当问题的答案具有单调性，就可以通过二分法把求解转换为判定。换句话说，二分法将原本从问题逐步求解出答案的过程，转换为在有序的候选答案中逐步查找的过程，直到判定某一候选答案符合问题条件，即得出问题的答案。

算法过程

通过以下示例说明二分法的算法过程：在一个升序数组中查找一个数。

  1. 考察当前查找范围内的中间元素，判断中间元素是否符合查找条件；
  2. 如果中间元素小于所查找的值，那么当前查找范围内所有左半部分的元素只会比中间元素更小，因此待查找的元素不会出现在左半部分，只需到右半部分继续查找，将查找范围缩小为右半部分，继续步骤 1；
  3. 同理，如果中间元素大于所查找的值，将查找范围缩小为左半部分，继续步骤 1；
  4. 如果中间元素符合查找条件，则查找成功，当前中间元素即为待查找的元素。
  5. 如果当前查找范围内已经不包含任何元素，则查找失败，原数组中不存在待查找的元素。

代码模板

在代码层面上，我们给出两种二分写法，分别用以处理不同的情况：

  1. 在单调递增序列 aa 中查找 ≥x\geq x 的数中最小的一个 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    vector<int> a; // 单调递增序列 a

    int l = 0, r = a.size(); // 查找区间为 [l, r)
    while(l < r){
        int mid = l + ((r - l) >> 1); // 防止 l + r 溢出
        if(a[mid] < x){ // 判定中间元素是否满足查找条件
            l = mid + 1; // 中间元素不符合条件，需要继续查找右半区间 [mid + 1, r) 是否有更优解
        }
        else{
            r = mid; // 中间元素符合条件，需要继续查找左半区间 [l, mid) 是否有更优解
        }
    }

    if(l == a.size()) ... // 序列 a 中不存在待查找的值
    else ... // a[l] 即为待查找的值
  2. 在单调递增序列 aa 中查找 ≤x\leq x 的数中最大的一个 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    vector<int> a; // 单调递增序列 a

    int l = -1, r = a.size() - 1; // 查找区间为 (l, r]
    while(l < r){
        int mid = l + ((r - l + 1) >> 1); // 防止 l + r 溢出，r - l + 1 是防止 r - l = 1 时出现死循环
        if(a[mid] <= x){ // 判定中间元素是否满足查找条件
            l = mid; // 中间元素符合条件，需要继续查找右半区间 (mid, r] 是否有更优解
        }
        else{
            r = mid - 1; // 中间元素不符合条件，需要继续查找左半区间 (l, mid - 1] 是否有更优解
        }
    }

    if(r == -1) ... // 序列 a 中不存在待查找的值
    else ... // a[l] 即为待查找的值

如何选择二分写法，关键在于通过分析具体问题，确定左右半部分哪一个是可行区间，以及中间元素应该归属于哪半部分。
最终，如果 l==rl == r，则查找成功，ll 即为答案所处的位置；如果 l>rl > r，则查找失败，原序列中不存在符合条件的元素。

具体应用

整数集合上的二分

在单调序列 aa 中（以非递减序列为例）查找数值 xx。

采用二分写法 1，即可查找到序列 aa 中数值 xx 第一次出现的位置。
采用二分写法 2，即可查找到序列 aa 中数值 xx 最后一次出现的位置。

实数集合上的二分

在实数区间 [start,end][start, end] 上查找满足条件的数值 xx。

1
2
3
4
5
6
7
8
9
10
11
12
13
// 写法一：固定最小精度
double l = start, r = end;
double eps = 1e-5; // 最小精度

while(l + eps < r){
    double mid = (l + r) / 2;
    if(check(mid)){ // 中间值 mid 满足查找条件，继续查找右半区间
        l = mid;
    }
    else{ // 中间值 mid 不满足查找条件，继续查找左半区间
        r = mid;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
// 写法二：固定二分次数
double l = start, r = end;
int maxn = 100; // 最大二分次数

for(int i = 0; i < maxn; i++){
    double mid = (l + r) / 2;
    if(check(mid)){ // 中间值 mid 满足查找条件，继续查找右半区间
        l = mid;
    }
    else{ // 中间值 mid 不满足查找条件，继续查找左半区间
        r = mid;
    }
}

一元三次方程求解

有形如：ax3+bx2+cx+d=0ax^3 + bx^2 + cx + d = 0 这样的一个一元三次方程。给出该方程中各项的系数（a,b,c,da,b,c,d 均为实数），并约定该方程存在三个不同实根（根的范围在 −100−100 至 100100 之间），且根与根之差的绝对值 ≥1≥1。要求由小到大依次输出这三个实根(一个根占一行)，并精确到小数点后 2 位。

令 f(x)=ax3+bx2+cx+df(x) = ax^3 + bx^2 + cx + d，即题目是求 f(x)=0f(x) = 0 的解，且三个答案都在 −100−100 至 100100 之间。
由于两个根的差的绝对值 ≥1≥1，保证了每一个大小为 1 的区间里至多有 1 个解，也就是说当大小为 1 的区间的两个端点的函数值异号时区间内一定有且只有一个解，同号时一定没有解。
那么可以枚举互相不重叠的每一个长度为 1 的区间，如果区间内有解，可以在区间内进行二分查找。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
int cnt = 0; // 记录已经找到的解的个数
double eps = 1e-3; // 最小精度
for(int i = -100; i < 100; i++){
    // 为防止重复，在区间 [l, r) 中寻找解
    double l = i;
    double r = i + 1.0;

    double fl = f(l);
    double fr = f(r);
    
    if(fl == 0){ // 判断左端点，如果是零点则直接输出
        printf("%.2lf\n", l);
        cnt++;
    }

    if(fl * fr < 0){ // 区间 [l, r) 中有解
        // 实数集合上的二分
        while(l + eps < r){
            double mid = (l + r) / 2;
            if(f(mid) * fr <= 0){ // 判断区间 [mid, r) 中是否有解
                l = mid; // 下一个查找区间是 [mid, r)
            }    
            else{
                r = mid;  // 下一个查找区间是 [l, mid)
            }    
        }
        printf("%.2lf\n", l); // 最终解在区间 [l, r) 中，输出左端点可以近似于解
        cnt++;
    }

    if(cnt == 3){ // 找到 3 个解，即可退出循环
        break;
    }
}

二分答案

一般而言，宏观的最优化问题可以抽象为函数，其“定义域”是这一问题下的解决方案，每个方案对应一个评估值来反映该方案的优劣程度，所有评估值构成函数的“值域”，最优解即为评估值最优的方案。
假设最优解的评估值为 ScoreScore，且评估值越高越优，则显然这一问题的值域存在「二段性」—— 当评估值小于等于 ScoreScore 时，一定存在一个该问题的可行方案；而当评估值大于 ScoreScore 时，一定不存在该问题的可行方案。
因此，可以通过二分法，将求最优解的问题，转换为在单调递增区间内（即函数值域）查找使得问题存在可行方案的最大评估值。在划分左右区间时，以问题是否存在可行方案作为条件，如果当前中间值 midmid，判定存在一个可行方案评分达到 midmid，则最优评估值一定大于 midmid，即在右半部分；反之，则右半部分的评估值一定都不存在一个可行方案，则最优评估值一定小于 midmid，即在左半部分。

这一类问题最经典的就是“最小值最大化”和“最大值最小化”。
以“最小值最大化”为例，要求满足某种条件的最小值的最大可能情况（最小值最大化）。
首先的想法是从大到小枚举这个作为答案的最小值，然后去判断这个值在问题条件的限制下是否存在合法方案，使得这个值在这个方案下是最小值。一旦枚举到某个值，使得问题存在合法方案，则这个值就是最大的“最小值”。若答案区间单调，就可以使用二分法来更快地找到答案。

这里的评估值就是这个“最小值”，要求这个数值越大越优。而问题存在可行方案，就是这个数值在这个可行方案中是最小值。

“最大值最小化”同理。

砍树

伐木工人需要砍 MM 米长的木材。现在有一台伐木机，工作流程如下：设置一个高度参数 HH（米），伐木机升起一个巨大的锯片到高度 HH，并锯掉所有树比 HH 高的部分（当然，树木不高于 HH 米的部分保持不变）。被锯下的部分可以作为木材。伐木工人非常关注生态保护，所以他不会砍掉过多的木材。这也是他尽可能高地设定伐木机锯片的原因。请帮助工人找到伐木机锯片的最大整数高度 HH，使得他能得到的木材至少为 MM 米。换句话说，如果再升高 11 米，他将得不到 MM 米木材。

问题可以转化为，在能够得到 MM 米木材的条件下，求可以设置的最大锯片高度 HH。
这一问题具有「二段性」。当锯片高度小于等于 HH 时，一定能够得到大于等于 MM 米的木材；而当锯片高度大于 HH 时，一定不能得到大于等于 MM 米的木材。
因此可以考虑以能否得到 MM 米木材作为条件二分锯片高度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
vector<int> height; // 树木的高度
int n; // 树木的数量
int m; // 至少需要的木材米数

bool check(int h){ // 二分时的判断条件，即当前锯片高度 h 能否得到大于等于 m 米的木材
    int wood = 0;
    for(int i = 0; i < n; i++){
        if(height[i] >= h){ // 高度高于 h 的树木，砍下高出的部分作为木材
            wood += height[i] - h;
        }
    }
    return wood >= m;
}

int l = 0, r = max_tree_height; // 查找区间为 [0, max_tree_height)，即 0 到所有树中最高的树高
while(l < r){
    int mid = l + ((r - l + 1) >> 1); // 防止 l + r 溢出，r - l + 1 是防止 r - l = 1 时出现死循环
    if(check(mid)){ // 判定中间元素是否满足查找条件
        l = mid; // 中间元素符合条件，需要继续查找右半区间是否有更优解
    }
    else{
        r = mid - 1; // 中间元素不符合条件，需要继续查找左半区间是否有更优解
    }
}

... // 循环结束，l 即为锯片的最大高度

三分

对于单峰函数，通常使用二分法衍生出的三分法求单峰函数的极值点。

单峰函数，是一类函数的总称，拥有唯一的极大值点，在极大值点左侧函数严格单调递增，右侧函数严格单调递减；或者拥有唯一的极小值点，在极小值点左侧函数严格单调递减，右侧函数严格单调递增。为避免混淆，也称后一种为单谷函数。

以求解单峰函数 ff 的极大值为例，函数定义域为 [start,end][start, end]。
三分法与二分法的基本思想类似，但每次操作需在当前区间 [l,r][l,r] 内任取两点 lmidlmid 和 rmidrmid（lmid<rmidlmid < rmid），把函数分为三部分。通过比较 f(lmid)f(lmid) 和 f(rmid)f(rmid) 的大小关系，确定极值的位置。

  1. 如果 f(lmid)<f(rmid)f(lmid) < f(rmid)，则 lmidlmid 和 rmidrmid 要么同时处于极大值点左侧（单调递增函数段），要么处于极大值点两侧。无论哪种情况下，极大值点都在 lmidlmid 右侧，则可以舍弃 lmidlmid 左侧区间（令 l=lmidl = lmid）。
  2. 同理，如果 f(lmid)>f(rmid)f(lmid) > f(rmid)，极大值点都在 rmidrmid 左侧，则可以舍弃 rmidrmid 右侧区间（令 r=rmidr = rmid）。
  3. 如果 f(lmid)=f(rmid)f(lmid) = f(rmid)，则 lmidlmid 和 rmidrmid 必定处于极大值点的两侧，此时既可以舍弃 lmidlmid 左侧区间，也可以舍弃 rmidrmid 右侧区间，二者取其一即可。

在实际选择三分点 lmidlmid 和 rmidrmid 时，如果取 lmidlmid 和 rmidrmid 为当前区间的三等分点，则区间范围每次缩小 1/31/3。为减少三分法的操作次数，应使每次舍弃的区间尽可能大。因此，在具体实现时，每一次操作的 lmidlmid 和 rmidrmid 分别取 mid−εmid-\varepsilon 和 mid+εmid+\varepsilon（midmid 为二等分点），这能够保证区间范围每次缩小接近 1/21/2，从而达到与二分法相近的时间复杂度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
double l = start, r = end;
double eps = 1e-5; // 最小精度

// 单峰函数 f(x)
double f(double x){
    double y = ...;
    return y;
}

// 三分法求解单峰函数的极大值点
while (r - l > eps) {
    double mid = (l + r) / 2;
    double lmid = mid - eps;
    double rmid = mid + eps;
    if (f(lmid) < f(rmid)){
        l = lmid;
    }
    else{
        r = rmid;
    }  
}

// 极大值点在 [l, r] 区间内