作为二分最经典的案例，猜价格——在电视节目中，用最少的次数猜出整数的物品价格。你的最优策略很可能就是二分方法的尝试。它的核心思想是，每次减少一半的搜索区间，以减少查找次数。
我们可以抽象出一个问题，从一个有序数组中找到等于 的元素的下标。根据中点值是高是低，决定下一次搜索哪一半区间。
// 查找元素在数组int a[]中的位置int binarySearch(int x) {int l = 0, r = n;while (l < r) {int m = l + (r - l) / 2; // 防止溢出 结果等于(l+r)/2if (a[m] == x) {return m;} else if (a[m] < x) {l = m + 1;} else if (a[m] > x) {r = m - 1;}}return -1;}
使用这种二分查找有一个条件，那就是数组必须有序，且元素必须唯一（否则有多个答案）。
为了元素的不唯一性，我们有如下模板：
二分查找模板
// 查找元素出现起始位置 （找不到返回-1）
int lower(int k) {
int l = 0, r = n - 1;
while (l < r) {
int m = l + r >> 1; // 右移1位等价于除以2，运算优先级低，此处不用打括号
if (a[m] < k) {
l = m + 1;
} else {
r = m;
}
}
return a[l] == k ? l : -1;
}
// 查找元素出现终止位置（找不到返回-1）
int upper(int k) {
int l = 0, r = n - 1;
while (l < r) {
int m = l + r + 1 >> 1; // 注意 + 1
if (a[m] > k) {
r = m - 1;
} else {
l = m;
}
}
return a[l] == k ? l : -1;
}
在这个模板的循环条件中，我们写成 while (l < r)，这样程序会在 l == r 时停止，a[l] 就是程序没有看到的最后一个元素，再进行一个判断即可。
二分有「细节是魔鬼」的说法。模板能很好的解决边界问题，请务必熟记，避免自行书写出现失误。注意，只要出现 l = m; 语句时（后一种模板）， 的值应该更新为
%20%2F%202#card=math&code=%28l%20%2B%20r%20%2B%201%29%20%2F%202&id=R9Anw)，防止无限循环，有关这个细节请自行查阅资料。
例题 1：蓝桥 算法训练 找数2
问题描述：在一个小到大的有序序列中（不存在重复数字），查找某个数所在的位置。如果该数不在该数列中，输出其应插入点的位置。
输入说明
第一行输入N表示有N个数据（N<=1000)
第二行N个小到大非重复的数字（<=10000)
第三行数字X，查找X输出说明
若X在序列中则输出其相应的位置，若不在序列中输出其应插入的位置。
样例输入 10 12 34 56 78 88 99 101 134 145 233 88
样例输出 5
样例输入 10 23 34 56 78 99 123 143 155 167 178 128
样例输出 7
说明：保证输入数据是有序的。
来试试看吗？这完全用到了刚刚提到的二分查找。尝试过之后再来看参考代码吧。
参考代码 1
#include <bits/stdc++.h>
using namespace std;
const int N = 1004;
int a[N];
int n;
int lower(int k) {
int l = 1, r = n + 1;
while (l < r) {
int m = l + r >> 1;
if (a[m] < k) {
l = m + 1;
} else {
r = m;
}
}
return l;
}
int main() {
cin >> n;
for (int i=1; i<=n; ++i) {
cin >> a[i];
}
int x;
cin >> x;
cout << lower(x) << endl;
return 0;
}
我猜你刚刚提交答案错误了不止一次，看过代码过后，不会想打我吧？这怎么和说好的不一样呢，你这模板有问题啊。其实，这就是模板，模板不是用来生搬硬套的，模板只是一个一般情况，是需要理解、并作出调整。这算是一个小玩笑，希望你记住这一点，往后我不会再做错误的引导。
首先，比较明显的不同是「如果该数不在该数列中，输出其应插入点的位置」，这一点其实暗示我们使用 lower() 模板，并在 return 语句时，a[l] != k 的情况也 return l; 而不是 return -1;
其次，答案应是「第几个位置」的逻辑序号，而不是数组下标，应当从 1 开始，我们的做法是读入数组就从下标为 1 的位置开始，这样两种序号就一致了。
另外，lower() 中的 l 和 r 也需要设为「可能为答案的区间」即 。举个例子，在
{1, 2, 3}, n = 3;中搜索 4 ，答案是 4。也就是说，第 种可能的位置在数组的最后，是存在的。
希望你对二分有了更好地理解。
实际上，二分的应用不局限于元素有序，它的充分必要条件其实是待搜索答案区间的「两段性质」，即在区间上存在唯一的一个点，使得这个点一侧的答案全部满足条件、另一侧的答案全部不满足条件。根据二分的核心思想，不断判断中点是否全部满足条件，每次减少一半的搜索区间，我们就能搜索到这个分界点。
这就是另一种二分的常见应用——二分答案。
二分答案问题常见的题面是，求满足条件的答案的最大/最小取值。
例题 2：力扣 278. 第一个错误的版本
你是产品经理，目前正在带领一个团队开发新的产品。不幸的是，你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的，所以错误的版本之后的所有版本都是错的。
假设你有
n个版本[1, 2, ..., n]，你想找出导致之后所有版本出错的第一个错误的版本。你可以通过调用
bool isBadVersion(version)接口来判断版本号version是否在单元测试中出错。实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数。示例 1： 输入：n = 5, bad = 4 输出：4 解释： 调用 isBadVersion(3) -> false 调用 isBadVersion(5) -> true 调用 isBadVersion(4) -> true 所以，4 是第一个错误的版本。
示例 2： 输入：n = 1, bad = 1 输出：1
提示：
在这种问题中，只需将验证 的条件从判断数字大小，改为判断是否符合条件的
check() 函数此题中直接给出了 check 函数，但这个函数一般需要根据题意自行编写，可能需要额外的逻辑。
参考代码 2-1
// The API isBadVersion is defined for you.
// bool isBadVersion(int version);
class Solution {
public:
int firstBadVersion(int n) {
int l = 1, r = n;
while (l < r) {
int m = l + (r - l) / 2;
if (isBadVersion(m)) {
r = m;
} else {
l = m + 1;
}
}
return l;
}
};
二分答案模板
// 满足条件最小值
int lower() {
int l = 0, r = n - 1;
while (l < r) {
int m = l + r >> 1;
if (check(m)) {
l = m + 1;
} else {
r = m;
}
}
return a[l] == k ? l : -1;
}
// 满足条件最大值
int upper() {
int l = 0, r = n - 1;
while (l < r) {
int m = l + r + 1 >> 1;
if (check(m)) {
r = m - 1;
} else {
l = m;
}
}
return a[l] == k ? l : -1;
}
时间复杂度：#card=math&code=O%28%5Clog%20n%29&id=lRWnX)
深入理解：写对二分查找不是套模板并往里面填空，需要仔细分析题意
练习：蓝桥 分巧克力【第八届】【省赛】
儿童节那天有K位小朋友到小明家做客。小明拿出了珍藏的巧克力招待小朋友们。
小明一共有N块巧克力，其中第i块是Hi x Wi的方格组成的长方形。为了公平起见，小明需要从这 N 块巧克力中切出K块巧克力分给小朋友们。切出的巧克力需要满足：
- 形状是正方形，边长是整数
2. 大小相同例如一块6x5的巧克力可以切出6块2x2的巧克力或者2块3x3的巧克力。
当然小朋友们都希望得到的巧克力尽可能大，你能帮小Hi计算出最大的边长是多少么？
输入格式
第一行包含两个整数N和K。(1 <= N, K <= 100000)
以下N行每行包含两个整数Hi和Wi。(1 <= Hi, Wi <= 100000)
输入保证每位小朋友至少能获得一块1x1的巧克力。输出格式
输出切出的正方形巧克力最大可能的边长。
样例输入
2 10
6 5
5 6样例输出
2
思路：对于一个特定的边长 ，我们可以通过遍历
个巧克力块，求出可以切出正方形的数量，这个数量大于等于
时方案可行。我们可以二分这个边长
的范围，找到
令方案可行的最大值。
参考代码 2-2
#include <iostream>
using namespace std;
const int N = 100004;
struct Choco {
int h;
int w;
void read() { // 如果你直接 cin >> c[i].h... 就不用写这个
cin >> h >> w;
}
// 返回这一块能切出几个 m*m 的正方形
int cut(int m) {
return (h / m) * (w / m);
}
} c[N]; // 可以在这里直接声明一个数组
int n, k;
// 判断边长为 m 的情况，能否足够切出 k 块
bool check(int m) {
int res = 0;
for (int i=0; i<n; ++i) {
res += c[i].cut(m);
}
// cout << m << ',' << res << endl;
return res >= k;
}
int main() {
cin >> n >> k;
for (int i=0; i<n; ++i) {
c[i].read(); // 这只是一种写法，你也可以写 cin >> c[i].h >> c[i].w;
}
int l = 1, r = N;
while (l < r) {
int mid = l + (r - l + 1) / 2;
if (check(mid)) {
l = mid;
} else {
r = mid - 1;
}
}
cout << l << endl;
return 0;
}
时间复杂度：#card=math&code=O%28n%5Clog%20m%29&id=iw9WZ)，
为巧克力块数量，
为边长取值范围。
例题 3：AcWing 790. 数的三次方根
给定一个浮点数
，求它的三次方根。
输入格式
共一行，包含一个浮点数
。
输出格式
共一行，包含一个浮点数，表示问题的解。
注意，结果保留
位小数。
数据范围
输入样例：
1000.00
输出样例：
10.000000
这道题二分计算的不再是整数，而是实数。我们通常的做法是，把搜索区间压缩到精度要求以内。
参考代码 3-1
#include <bits/stdc++.h>
using namespace std;
const double eps = 1e-8;
double x;
int main() {
cin >> x;
double l = -10000, r = 10000;
while (r - l > eps) {
double m = (l + r) / 2;
if (m * m * m - x > 0) {
r = m;
} else {
l = m;
}
}
cout << fixed << setprecision(6) << l << endl;
return 0;
}
代码 cout << fixed << setprecision(6) << l << endl; 的写法是 C++ 格式化输出小数的方法，fixed表示末尾补零，setprecision 中的参数表示小数位数。
代码中使用到 eps （epsilon），表示大于零的一个很小的数。它在浮点数比较时也经常使用——由于浮点数存在误差，不能直接用 == 比较。通常做法如下：
const double eps = 1e-7;
bool equal(double a, double b) {
return fabs(a - b) < eps; // fabs() 取浮点数绝对值
}
在题目没有明确指出时，一般认为两数相差小于 的情况就足够精确。
同理，由于浮点数的误差，我们通常写平方、立方时不写 pow(x, 2) 或 pow(x, 3)，而写成连续相乘的形式。
练习：[NOIP2001]一元三次方程求解
题目描述
有形如：ax3+bx2+cx+d=0 这样的一个一元三次方程。给出该方程中各项的系数(a，b，c，d 均为实数)，并约定该方程存在三个不同实根(根的范围在-100至100之间)，且根与根之差的绝对值 ≥ 1。要求由小到大依次在同一行输出这三个实根(根与根之间留有空格)，并精确到小数点后2位。
提示：记方程f(x) = 0，若存在2个数x1和x2，且x1 < x2，f(x1)*f(x2) < 0，则在(x1，x2)之间一定有一个根。输入描述:
一行，4个实数A,B,C,D。
输出描述:
一行，3个实根，并精确到小数点后2位。
输入
1 -5 -4 20
输出
-2.00 2.00 5.00
思路：由于「根与根之差的绝对值 ≥ 1」，把根的范围（在-100至100之间）分割成长度为 1 的区间，并枚举这些区间，在每一个区间 #card=math&code=%28l%2C%20r%29&id=F8NyP) 内如果有
%5Ccdot%20f(r)%20%3C%200#card=math&code=f%28l%29%5Ccdot%20f%28r%29%20%3C%200&id=yDSpg) ，说明存在根，则二分搜索找到答案。最后，题目要从小到大顺序输出，所有整数的区间分界点需要在枚举的同时判断。
参考代码 3-2
#include <bits/stdc++.h>
using namespace std;
double a, b, c, d;
double f(double x) {
return a*x*x*x + b*x*x + c*x + d;
}
int main() {
cin >> a >> b >> c >> d;
cout << fixed << setprecision(2);
for (int i=-100; i<100; ++i) {
// 判断区间分界点
if (f(i) == 0) {
cout << 1. * i << ' '; // 乘以 1.0 转为 double 类型，满足输出精度
}
// 判断区间是否有根
if (f(i) * f(i + 1) < 0) {
double l = i, r = i + 1;
while (r - l > 0.001) {
double m = (l + r) / 2;
if (f(l) * f(m) < 0) {
r = m;
} else {
l = m;
}
}
cout << l << ' ';
}
}
// 单独判断最后一个区间的末尾
if (f(100) == 0) {
cout << 100.; // 同样，100.0 是 double 类型
}
return 0;
}
若有收获，就点个赞吧
0 人点赞
