由于本人经常忘记二分查找的要点，因此便对其进行了整理总结。
部分参考了 yxc 和 0x3f 的教学内容。
前言 #
二分查找在面试与竞赛中都十分常见。
虽然算法难度不高。但不熟练的情况下会很容易出现边界错误而浪费时间。
在复杂的综合题中，也可以会忘记使用二分查找，而导致超时。
二分模板 #
二分最经典的情景，在单调数组中找目标值。
# 第一个大于等于 target 的位置
# 等价于最常用的 lower_bound(a.begin(), a.end(), target)
l = 0
r = n - 1
while l < r :
mid = l + r >> 1
if nums[mid] < target:
l = mid + 1
else:
r = mid
return l
# 第一个大于 target 的位置
# 等价于 upper_bound(a.begin(), a.end(), target)
l = 0
r = n - 1
while l < r :
mid = l + r >> 1
if nums[mid] <= target:
l = mid + 1
else:
r = mid
return l
# 最后一个小于等于 target 的位置
# 等价于的 lower_bound(a.begin(), a.end(), target, greater<int>())
l = 0
r = n - 1
while l < r :
mid = l + r + 1 >> 1
if nums[mid] < target:
l = mid
else:
r = mid - 1
return l
# 最后一个小于 target 的位置
# 等价于最常用的 upper_bound(a.begin(), a.end(), target, greater<int>())
l = 0
r = n - 1
while l < r :
mid = l + r + 1 >> 1
if nums[mid] <= target:
l = mid
else:
r = mid - 1
return l
二分的库函数 #
对于 C++ 而言：
#include<bits/stdc++.h>
#include<algorithm> // 具体头文件
vector<int> a = {1, 2, 3, 4, 4, 5, 6};
int target = 4;
// 对 vector 二分，库返回的是迭代器
auto it1 = lower_bound(a.begin(), a.end(), target);
auto it2 = upper_bound(a.begin(), a.end(), target);
// 其实 greater 就是把数组反过来查找
auto it3 = lower_bound(a.begin(), a.end(), target, greater<int>());
auto it4 = upper_bound(a.begin(), a.end(), target, greater<int>());
int pos = it1 - a.begin();
对于 python 而言：
import bisect
a = [1, 2, 3, 4, 4, 5, 6]
target = 4
# 分别对应 lower_bound 和 upper_bound
pos1 = bisect.bisect_left(a, target)
pos2 = bisect.bisect_right(a, target)
# Python 没有原生的降序 bisect，只能自己写下面两个
二分答案 #
根据经验，当题目中出现求最小、求最大、最大化最小、最小化最大时，很有可能要对答案进行二分查找。
在二分答案时候，要时刻注意：
-
r 的初始值是什么？即答案的上界。（如果在比赛中，上界开大一些更稳妥）
-
check() 条件对应的边界是哪种？
- 一般而言，check(int x) 按正常的 bool 逻辑写。
- 即 x 满足条件为 true，不满足为 false。
- 而在 while 查找中，用 !check()，代替第一种二分的 if 条件。
-
问题有没有单调性，能不能用二分？
- 如果没有单调性，一般是 DP 或 搜索。
绝大部分二分答案的上界都在 int 范围外
因此千万别忘了 mid 开 long long
求最小 - 修车的最少时间： #
给你一个整数数组 ranks ，表示一些机械工的 能力值 。ranksi 是第 i 位机械工的能力值。能力值为 r的机械工可以在 r * n2 分钟内修好 n 辆车。
同时给你一个整数 cars ，表示总共需要修理的汽车数目。
请你返回修理所有汽车 最少 需要多少时间。
注意： 所有机械工可以同时修理汽车。
示例 1：
输入：ranks = [4,2,3,1], cars = 10
输出：16
解释：
- 第一位机械工修 2 辆车，需要 4 * 2 * 2 = 16 分钟。
- 第二位机械工修 2 辆车，需要 2 * 2 * 2 = 8 分钟。
- 第三位机械工修 2 辆车，需要 3 * 2 * 2 = 12 分钟。
- 第四位机械工修 4 辆车，需要 1 * 4 * 4 = 16 分钟。
16 分钟是修理完所有车需要的最少时间。
示例 2：
输入：ranks = [5,1,8], cars = 6
输出：16
解释：
- 第一位机械工修 1 辆车，需要 5 * 1 * 1 = 5 分钟。
- 第二位机械工修 4 辆车，需要 1 * 4 * 4 = 16 分钟。
- 第三位机械工修 1 辆车，需要 8 * 1 * 1 = 8 分钟。
16 分钟时修理完所有车需要的最少时间。
提示：
1 <= ranks.length <= 1051 <= ranks[i] <= 1001 <= cars <= 106
题解：
# 经典二分答案
class Solution:
def repairCars(self, ranks: List[int], cars: int) -> int:
def check(x : int) -> bool:
car_num = 0
for rank in ranks:
car_num += int(sqrt(x / rank))
return car_num >= cars
l, r = 0, int(1e15)
while l < r:
mid = l + r >> 1
if not check(mid):
l = mid + 1
else:
r = mid
return l
最小化最大 - 袋子里最少数目的球： #
给你一个整数数组 nums ，其中 nums[i] 表示第 i 个袋子里球的数目。同时给你一个整数maxOperations 。
你可以进行如下操作至多 maxOperations 次：
- 选择任意一个袋子，并将袋子里的球分到 2 个新的袋子中，每个袋子里都有正整数个球。
- 比方说，一个袋子里有
5个球，你可以把它们分到两个新袋子里，分别有1个和4个球，或者分别有2个和3个球。
你的开销是单个袋子里球数目的 最大值 ，你想要 最小化 开销。
请你返回进行上述操作后的最小开销。
示例 1：
输入：nums = [9], maxOperations = 2
输出：3
解释：
- 将装有 9 个球的袋子分成装有 6 个和 3 个球的袋子。[9] -> [6,3] 。
- 将装有 6 个球的袋子分成装有 3 个和 3 个球的袋子。[6,3] -> [3,3,3] 。
装有最多球的袋子里装有 3 个球，所以开销为 3 并返回 3 。
示例 2：
输入：nums = [2,4,8,2], maxOperations = 4
输出：2
解释：
- 将装有 8 个球的袋子分成装有 4 个和 4 个球的袋子。[2,4,8,2] -> [2,4,4,4,2] 。
- 将装有 4 个球的袋子分成装有 2 个和 2 个球的袋子。[2,4,4,4,2] -> [2,2,2,4,4,2] 。
- 将装有 4 个球的袋子分成装有 2 个和 2 个球的袋子。[2,2,2,4,4,2] -> [2,2,2,2,2,4,2] 。
- 将装有 4 个球的袋子分成装有 2 个和 2 个球的袋子。[2,2,2,2,2,4,2] -> [2,2,2,2,2,2,2,2] 。
装有最多球的袋子里装有 2 个球，所以开销为 2 并返回 2 。
示例 3：
输入：nums = [7,17], maxOperations = 2
输出：7
提示：
1 <= nums.length <= 1051 <= maxOperations, nums[i] <= 109
题解：
class Solution:
def minimumSize(self, nums: List[int], maxOperations: int) -> int:
def check(x : int) -> bool:
if x == 0:
return False
operation = 0
for num in nums:
if num > x:
operation += (num + x - 1) // x - 1 # 向上取整后减一
return operation <= maxOperations
l, r = 0, int(1e9)
while l < r:
mid = l + r >> 1
if not check(mid):
l = mid + 1
else:
r = mid
return l
最大化最小 - 范围内整数的最大得分： #
给你一个整数数组 start 和一个整数 d，代表 n 个区间 [start[i], start[i] + d]。
你需要选择 n 个整数，其中第 i 个整数必须属于第 i 个区间。所选整数的 得分 定义为所选整数两两之间的最小 绝对差。
返回所选整数的 最大可能得分 。
示例 1：
输入： start = [6,0,3], d = 2
输出： 4
解释：
可以选择整数 8, 0 和 4 获得最大可能得分，得分为 min(|8 - 0|, |8 - 4|, |0 - 4|)，等于 4。
示例 2：
输入： start = [2,6,13,13], d = 5
输出： 5
解释：
可以选择整数 2, 7, 13 和 18 获得最大可能得分，得分为 min(|2 - 7|, |2 - 13|, |2 - 18|, |7 - 13|, |7 - 18|, |13 - 18|)，等于 5。
提示：
2 <= start.length <= 1050 <= start[i] <= 1090 <= d <= 109
题解：
// 24.9.8 注释： 对二分板子不熟悉 导致花了很长时间
class Solution {
public:
bool check(int mid, vector<int>& start, int d) {
int n = start.size();
long long mn = start[0];
for (int i = 1; i < n; i++) {
// 改了一个小时没改出来 max 这行 还得多学学
mn = max(1LL * start[i], mn + mid);
if (mn <= start[i] + d) {
continue;
}
return false;
}
return true;
}
int maxPossibleScore(vector<int>& start, int d) {
int n = start.size();
sort(start.begin(), start.end());
// 上边界二分的写法不能忘啊
long long l = 0, r = long(2e9);
while (l < r) {
long long mid = l + r + 1 >> 1;
if (!check(mid, start, d)) {
r = mid - 1;
} else {
l = mid;
}
}
return l;
}
};
二分作为解题步骤之一 #
二分经常作为解题中的某一步，经常和其他算法结合考察。
前缀和 - 青蛙过河 #
小青蛙住在一条河边，它想到河对岸的学校去学习。
小青蛙打算经过河里的石头跳到对岸。
河里的石头排成了一条直线，小青蛙每次跳跃必须落在一块石头或者岸上。
不过，每块石头有一个高度，每次小青蛙从一块石头起跳，这块石头的高度就会下降 1，当石头的高度下降到 0 时小青蛙不能再跳到这块石头上（某次跳跃后使石头高度下降到 0 是允许的）。
小青蛙一共需要去学校上 x 天课，所以它需要往返 2x 次。 当小青蛙具有一个跳跃能力 y 时，它能跳不超过 y 的距离。 请问小青蛙的跳跃能力至少是多少才能用这些石头上完 x 次课。
输入格式
输入的第一行包含两个整数 n, x，分别表示河的宽度和小青蛙需要去学校的天数。请注意 2x 才是实际过河的次数。
第二行包含 n−1 个非负整数 H1, H2, ⋅⋅⋅, Hn−1，其中 Hi > 0 表示在河中与小青蛙的家相距 i 的地方有一块高度为 Hi 的石头，Hi = 0 表示这个位置没有石头。
输出格式
输出一行，包含一个整数，表示小青蛙需要的最低跳跃能力。
数据范围
对于所有评测用例，1 ≤ n ≤ 10⁵, 1 ≤ x ≤ 10⁹, 0 ≤ Hi ≤ 10⁴。
输入样例
5 1
1 0 1 0
输出样例
4
样例解释
由于只有两块高度为 1 的石头，所以往返只能各用一块。
第 1 块石头和对岸的距离为 4，如果小青蛙的跳跃能力为 3 则无法满足要求。
所以小青蛙最少需要 4 的跳跃能力。
题解
// 找规律 + 前缀和 + 二分查找
// 核心是先找到为了让青蛙能踩到对应的石头，满足 i 块到 i + step 块石头的和大于 2 * x 即可
// 多次求区间之和自然想到前缀和
// 多次求位置的 step 并且符合二段性 自然考虑二分查找
// 此题要实现的细节挺多的 要注意
#include <bits/stdc++.h>
using namespace std;
int n, x;
vector<int>stone;
vector<long long>prefix;
bool check(int step) {
// 注意上界为 n - step
for (int i = 0; i < n - step + 1; i++) {
if (prefix[i + step] - prefix[i] < 2 * x) {
return false;
}
}
return true;
}
int main () {
cin >> n >> x;
n--;
stone.resize(n);
for (int i = 0; i < n ;i++) {
cin >> stone[i];
}
prefix.resize(n + 1);
prefix[0] = 0;
for (int i = 1; i <= n; i++) {
prefix[i] = prefix[i - 1] + stone[i - 1];
// cout << prefix[i] << " ";
}
int l = 0, r = n + 100;
while(l < r) {
int mid = l + r >> 1;
// cout << mid << " ";
if (!check(mid))
l = mid + 1;
else
r = mid;
}
cout << l;
return 0;
}