上一篇1. 数组查值；2. 解的可行性判断。

这两个题型其一是经典的二分搜索的场景，基本上是所有教科书上都是二分搜索的提出场景。所以在文章中并没有详细的结束其过程，只推荐了边界判断条件 while (l <= r) 并且在边界判断的时候以 mid == target 作为循环终点。

其二是二分搜索的常见题型，一般都是给出一个数据范围，这个范围可能是推导出来的，也可能是变量类型的上下界，并且你可以推导出 target 以及变量 x 的关系式，当关系呈单调关系之后，就可以在变量范围内二分寻求可行性解。

最大值最小化问题

最大值最小化，相对相同的题型还有最小化最大值。在某些教科书上也有叫：Max-Min 问题。用比较简短的描述来说，Max-Min 问题主要是为了提升优化目标中表现最差的成分。

通过概念，也许你无法想象是什么样的题型。同样的，我们通过一道例题来讲解这个类型：

农夫搭了一间有 N 间牛舍的小屋。牛舍排在一条线上，第 i 号牛舍在 xi 的位置，但是他的 M 头牛对小屋很不满意，因此经常相互攻击。农夫为了防止牛之间的相互伤害，因此他决定把每头牛都放在离其他牛尽可能远的牛舍。也就是要最大化最近的两头牛之间的距离。(POJ-2456)

给出一组样例，有 N = 5 间牛舍，牛舍的坐标数组 x = {1, 2, 8, 4, 9}，有 M = 3 头牛。最后我们输出 3，因为我们将牛放在 {1, 4, 9} 这三个牛舍，且最近的两头牛距离 4 - 1 = 3 个单位位置。

根据上一篇二分问题的解题套路，我们设 “两头牛的距离不小于 Target”。有了这个 Target 之后，我们一次遍历来判断是否能将所有的牛通过这个最小距离 Target 而安排到牛舍里。根据是否合法来当作边界变化的条件。

梳理一下整个过程：

1. 对牛舍的位置 x 进行排序；

2. 把第一头牛放入 x1 的牛舍；

3. 如果第 i 头牛放入了 xj 的话，第 i + 1 头牛就要放入满足 xj + Target ≤ xk 的最小的 xk 中；

4. 判断是否可行，进行二分边界转换

这里不得不提及一下，我们第一步是对牛舍进行排序，在第四步中，通过尝试这个“最大化最小距离”，其实也是利用了贪心的策略。因为我们保证了这个最小距离，所以如果每个牛都按照这个距离间隔，那么在牛舍中一定能装下。

按照这四个步骤，其实我们就可以通过二分的方法进行求解。

#include <math.h>
#include <cstdio>
#include <algorithm>
using namespace std;
    
int N, C;
long long sta[100005];
long long r;
    
bool check(long long d) {
    int l = 0;
    for (int i = 1; i < C; ++ i) {
        int crt = l + 1;
				// 依次判断是否能装下至少间隔为 d 的 C 个牛
        while (crt < N && sta[crt] - sta[l] < d) {
            crt ++;
        }
        if (crt == N) {
            return false;
        }
        l = crt;
    }
    return true;
}
    
int main() {
    scanf("%d %d", &N, &C);
    for (int i = 0; i < N; ++ i) {
        scanf("%d", &sta[i]);
        r = max(r, sta[i]);
    }
    
    sort(sta, sta + N);
    long long l = 0;
    while (l <= r) {
        int mid = l + (r - l) / 2;
        if (check(mid)) {
            l = mid + 1;
        } else {
            r = mid - 1;
        }
    }
    printf("%d\n", r);
}

总结一下最大值最小化问题的解题思路：

1. 问题场景仍旧设立在找出一个可行性的解，但是这个解是极值化的；

2. 需要求的解肯定和题目中的某个直接变量或者推导变量有某种单调关系；

3. 套用二分的思想，缩小搜索范围。

其实我们发现最大值最小化问题就是可行性解的一种特殊类型，往往这种题目与贪心策略会一起使用。所以当总体复杂度我们确定是 O(nlogn) 的时候，此时我们可以考虑通过排序来预处理题目中给定的数组，在查找的时候建立一个游标来进行贪心策略排查。

最大化平均值问题

有 n 个物品的重量和价值分别是 wi 和 vi。从中选出 k 个物品使得单位重量的价值最大。

给出一个样例，n = 3、k = 2、(w, v) = [(2, 2), (5, 3), (2, 1)]。如果我们选择 0 号和 2 号物品，平均价值是：

拿到这道题目，首先想到的方法是把物品按照单位价值进行排序，然后从大到小贪心地进行选取。但是这个方法对于样例输入则会得到 5 / 7 = 0.714，所以这个方法是不可行的。我们来证明一下这两个式子的差异化。

首先是直接求解每一个物品的均值，然后相加：

再者是题目中的先选取 k 个，再计算整体均值：

所以通过判断每个物品的单位价值，是无法反应总体单位价值的多少的。因为表达式都完全不同。知道了这些，我们从整体均值的式子入手。

我们继续来求解一下这道题的 Target，设待求解 x 表示 可以选择使单位重量的价值不小于 x，可以看出我们将原问题转化成了满足 T(x) 的最大 x 取值。

假设我们求得的 S 集合就是我们要取的物品，根据题意需要求解的式子来列写一下解答方程：

我们来对这个表达式变型：

我们假设下面这个式子为 K：

那么只要对 K = vi - x * wi 这个式子在给定 x 的情况下降序排序，然后贪心选取前 k 个是不是就可以了？答案是肯定的。我们发现 K 目标值要大于等于 0 ，这也就是我边界的转换条件，使其不断向 0 逼近即可。

#include <math.h>
#include <cstdio>
#include <algorithm>
using namespace std;
const double eps = 1e-6;
const int maxn = 1e5;
const double inf = 1e6;
    
int n, k;
int w[maxn], v[maxn];
double K[maxn];
    
bool check(double x) {
    for (int i = 0; i < n; ++ i) {
        K[i] = v[i] - x * w[i];
    }
    sort(K, K + n);
    
    // 计算 K 中从大到小的 k 个和
    double sum = 0;
    int cnt = 0, cur = n - 1;
    while (cnt != k) {
        sum += K[cur --];
        cnt ++;
    }
    return sum >= 0;
}
    
int main() {
    scanf("%d %d", &n, &k);
    for (int i = 0; i < n; ++ i) {
        scanf("%d %d", &w[i], &v[i]);
    }
    double l = 0, r = inf;
    while (fabs(l - r) > eps) {
        double mid = (l + r) / 2;
        // 由于结果和传入值 x 呈反比，所以符合条件的情况下区间右移使其趋于0
        // K = v - x * w
        if (check(mid)) {
            l = mid;
        }
        else {
            r = mid;
        }
    }
    printf("%.2lf\n", l);
}

总结一下最大化平均值问题的求解思路：

1. 设答案 x 已知，根据题目列写关系式；

2. 确定 x 在某个可解不等式或者等式中的单调性；

3. 在 x 的取值范围内二分结果，区间转移判断由题目条件决定。

二分问题小结

这四种问题应该是最常见的二分问题类型了。总结一下他们的共性，其实都是在确定目标值和自变量的单调性，然后确定范围边界来进行二分缩小自变量的取值范围，从而夹逼出一个结果值。所以二分搜索不仅仅是值的查找，而是为了确定某个解区别于穷举且效率更高的一种搜索手段。由于自身外层的复杂度是 O(logN) ，所以内层的判断边界转移的方法，我们可以使用 O(N) 甚至是 O(NlogN) 复杂度的代码来决策这个转移条件（假定数据量在 10^6 左右，一般需要二分的题目都在这个数量级范围）。当然所有的前提都是有单调、有范围这两个因素下。