vlambda博客
学习文章列表

讲了二分查找的实现方式和注意细节，本文接着讲二分查找在笔试面试题中的常见题型和实用技巧。

1.最大值最小（最小值最大）

这类题都有明显的关键字特征，求”最小的最大值“，”最大的最小值“，可以考虑用二分来做。

下面给出模板题：

给定一个长度为n的正整数数组 a，将其分成连续的 m 段，使得每段和的最大值最小，输出该最小的最大值。

数据范围：1 < m <= n < 1e5, 0 < ai < 10000

样例：

输入：

5 3

4 2 4 5 1

输出：

6

我们实现一个 check 函数，功能是”判断数组能否被分成 m 段，其中至少有一段的和大于等于 x“。

显然，我们要求的答案就是最后一个满足 check 函数的 x 的值。就变成了上一篇文章的。

现在关键就在于，如何高效地实现 check 函数？

可以贪心地考虑：我们把数组 a 从前往后依次分组，使得每组之和都刚好小于x，即加上后一个数就变成大于等于 x 的。如果这样分成 m 组后，仍有多余的数，则说明至少存在一组的和大于等于 x，时间复杂度为 O(n)。

下面给出核心代码：

bool check(int x){ int s = 0, cnt = 0; for(int i = 0; i < n; i++) {        //若单个元素就 >= x 那一定存在        if(a[i] >= x)    return true;   if(s + a[i] < x) s += a[i]; else cnt++, s = a[i]; } return cnt >= m;}
int l = 0, r = 1e9;while(l < r){ int mid = l + r + 1 >> 1; if(check(mid)) l = mid; else r = mid - 1;}

整体复杂度为 O(nlogn)。这里偷了下懒，扩大了 l 和 r 的范围。实际上 log1e9 < 30，扩大范围并不会增加几次循环。

本题思维上还是有一点难度的，尤其是 check 函数的实现，请大家好好理解。

2.问题答案具有单调性（二分性）

什么叫答案具有单调性？

可以理解为，如果一个值满足题目中的要求，那么所有大于（或者小于）这个值的数都会满足要求，就可以考虑用二分来做。

与上一题类似，只是没有明显的关键词提示。下面给出模板题：

给定一个长度为 n 的正整数数组 a 以及一个整数 k，其中 n 为奇数。每次操作可以使得其中一个数加 1，最多可进行 k 次操作。求可能得到的最大中位数。

数据范围：1 <= n, ai, k <= 1e5

样例：

输入：
3 2 

2 6 4

输出：
6

类似地，我们可以实现一个 check(x) 函数，功能是”判断数组 a 经过不超过 k 次操作的中位数是否大于等于 x“。

考虑 check 函数的实现，首先要对数组排个序，中位数位置为 (n + 1) / 2（下标从1开始），

添加在中位数之前的数，都可以添加到中位数之后去，因此只要保证 最少要添加的值 小于等于 k 就行了。下面给出核心代码：

bool check(int x) {    long long s = 0; //注意数据可能爆int for (int i = (n + 1) / 2; i <= n; ++i) if (a[i] < x) s += x - a[i]; else break; return s <= k;}
int l = 0, r = 1e5;while(l < r){    int mid = l + r + 1 >> 1; if(check(mid)) l = mid; else r = mid - 1;}

当然，求阴影部分的值也可以用二分（最后一个小于 x 的位置）加前缀和优化到 O(logn)，但本题是需要排序的，上限已经到了 O(nlogn)，没必要再去优化了。

3.小结

通过上面两道题，我们可以发现：二分法的精髓在于把一个”求解问题“转化为”判定问题“，而通常”判定问题“的难度是远远小于”求解问题“的。

只需要一个问题的答案满足有界性和单调性（二分性），即在有限的不同的连续区间上有不同的性质，就可以考虑使用二分（三分）来做。

最后，留给大家一道真实的笔试题练手：

给定 n 个长度为 Li 的绳子，现在需要 m 根等长的绳子，你可以对每根绳子任意裁剪，但不能拼接，求 m 根绳子的最长长度（保留两位小数）。

数据范围：1 <= n, m <= 1e5,  0 < Li < 1e9, Li为整数

样例：
输入：
3 4

3 5 4

输出：

2.50

提示：这是某条的一道笔试题，如果不在二分的标签下，可能很多人的第一映像是 贪心？模拟？DP？

其实，我们可以发现：如果 n 根绳子可以剪成 m 根长度为 k 的绳子，那一定可以剪成更小的。所以，原问题就转化成了求最后一个满足题意的数（注意浮点数的比较哦），下期给出标程。

--------------------------