如果这篇博客帮助到你，可以请我喝一杯咖啡~
CC BY 4.0 （除特别声明或转载文章外）
二分分为两种，浮点数二分和整数二分
浮点数二分相对简单，不需要考虑边界
一 浮点数二分
680. 剪绳子
有N根绳子，第i根绳子长度为Li，现在需要M根等长的绳子，你可以对N根绳子进行任意裁剪（不能拼接），请你帮忙计算出这M根绳子最长的长度是多少。
输入格式
第一行包含2个正整数N、M，表示原始绳子的数量和需求绳子的数量。
第二行包含N个整数，其中第 i 个整数Li表示第 i 根绳子的长度。
输出格式
输出一个数字，表示裁剪后最长的长度，保留两位小数。
数据范围
1≤N,M≤100000 0<Li<10^9
输入样例：
3 4
3 5 4
输出样例：
2.50
样例解释
第一根和第三根分别裁剪出一根2.50长度的绳子，第二根剪成2根2.50长度的绳子，刚好4根。
#include<cstdio>
#define N 100010
int n, m;
int Rope[N];
bool check(double mid)
{
int cnt = 0;
for(int i = 0; i < n; ++i)
{
// 总数加上 每一根绳子的长度 / mid（绳子的最长长度）
cnt += Rope[i] / mid;
if(cnt >= m) return true;
}
return false;
}
int main(void)
{
scanf("%d%d", &n, &m);
for(int i = 0; i < n; ++i)
scanf("%d", &Rope[i]);
double l = 0, r = 1e9;
while(r - l > 1e-4)
{
double mid = (l + r) / 2;
// 如果当前的 mid 可以满足分出 m 个绳子，那么绳子可以尝试更长的长度
if(check(mid)) l = mid;
else r = mid;
}
printf("%.2f\n", l);
return 0;
}
注意到 while 循环的判定条件为：while(r - l > 1e-4) 为什么是 1e-4 呢？
对于需要保留 k 位小数的结果，我们尝试到 1e-(2 + k) 即可
还有一种写法是：
int i = 100;
while(i--)
{
double mid = (l + r) / 2;
if(check(mid)) l = mid;
else r = mid;
}
尝试 100 次即可。
时间限制为 1s ，c/cpp 程序一秒大概可以计算 10^7 ~ 10^8 次，我们取较小的 10^7 。check 函数中的 whie 循环的复杂度是 10^5 ，那么 10^7/10^5 = 100 次是较为合理的
790. 数的三次方根
给定一个浮点数n，求它的三次方根。
输入格式
共一行，包含一个浮点数n。
输出格式
共一行，包含一个浮点数，表示问题的解。
注意，结果保留6位小数。
数据范围
−10000≤n≤10000−10000≤n≤10000
输入样例：
1000.00
输出样例：
10.000000
#include<cstdio>
#include<iostream>
double n;
bool check(double mid)
{
if(mid * mid * mid < n) return true;
return false;
}
int main(void)
{
scanf("%lf", &n);
double l, r;
if(n > 0)
{
l = 0;
r = n;
}
else
{
l = n;
r = 0;
}
while(r - l > 1e-8)
{
double mid = (r + l) / 2;
if(check(mid)) l = mid;
else r = mid;
}
printf("%.6f\n", l);
return 0;
}
二 整数二分
整数二分的两种模板
1)
int bsearch_1(int l, int r)
{
while (l < r)
{
int mid = l + r >> 1;
if (check(mid)) r = mid;
else l = mid + 1;
}
return l;
}
2)
int bsearch_2(int l, int r)
{
while (l < r)
{
int mid = l + r + 1 >> 1;
if (check(mid)) l = mid;
else r = mid - 1;
}
return l;
}
1227. 分巧克力
儿童节那天有 K 位小朋友到小明家做客。
小明拿出了珍藏的巧克力招待小朋友们。
小明一共有 N 块巧克力，其中第 i 块是 Hi×Wi 的方格组成的长方形。
为了公平起见，小明需要从这 N 块巧克力中切出 K 块巧克力分给小朋友们。
切出的巧克力需要满足：
- 形状是正方形，边长是整数
- 大小相同
例如一块 6×5 的巧克力可以切出 6 块 2×2 的巧克力或者 22 块 3×3 的巧克力。
当然小朋友们都希望得到的巧克力尽可能大，你能帮小明计算出最大的边长是多少么？
输入格式
第一行包含两个整数 N 和 K。
以下 N 行每行包含两个整数 Hi 和 Wi。
输入保证每位小朋友至少能获得一块 1×1 的巧克力。
输出格式
输出切出的正方形巧克力最大可能的边长。
数据范围
1≤N,K≤105 1≤Hi,Wi≤105
输入样例：
2 10
6 5
5 6
输出样例：
2
#include<cstdio>
#define N 100010
typedef long long LL;
int n, k;
int H[N], W[N];
bool check(int mid)
{
LL cnt = 0;
for(int i = 0; i < n; ++i)
{
cnt += (LL)(H[i] / mid) * (W[i] / mid);
if(cnt >= k) return true;
}
return false;
}
int main(void)
{
scanf("%d%d", &n, &k);
for(int i = 0; i < n; ++i)
{
scanf("%d%d", &H[i], &W[i]);
}
int l = 1, r = (int)1e5;
while(l < r)
{
// 向上取整
int mid = l + r + 1>> 1;
if(check(mid)) l = mid;
else r = mid - 1;
}
printf("%d\n", l);
return 0;
}
注意这道题不能写成：
while(l < r)
{
// 向下取整
int mid = l + r >> 1;
if(check(mid)) l = mid + 1;
else r = mid;
}
考虑最后的区间 [2,3] 如果 2 是答案的话，这么写会错过最终的答案 2 。退出循环时 l == r == 3
789. 数的范围
给定一个按照升序排列的长度为n的整数数组，以及 q 个查询。
对于每个查询，返回一个元素k的起始位置和终止位置（位置从0开始计数）。
如果数组中不存在该元素，则返回“-1 -1”。
输入格式
第一行包含整数n和q，表示数组长度和询问个数。
第二行包含n个整数（均在1~10000范围内），表示完整数组。
接下来q行，每行包含一个整数k，表示一个询问元素。
输出格式
共q行，每行包含两个整数，表示所求元素的起始位置和终止位置。
如果数组中不存在该元素，则返回“-1 -1”。
数据范围
1≤n≤100000 1≤q≤10000 1≤k≤10000
输入样例：
6 3
1 2 2 3 3 4
3
4
5
输出样例：
3 4
5 5
-1 -1
一开始我写的（错的）
#include<cstdio>
int n, q;
int a[100010];
void Find(int tar)
{
int l = 0, r = n - 1;
while(l < r)
{
int m = (l + r + 1) >> 1;
if(a[m] >= tar) r = m - 1;
else l = m;
}
int left = l + 1;
l = left;
r = n - 1;
while(l < r)
{
int m = (l + r) >> 1;
if(a[m] <= tar) l = m + 1;
else r = m;
}
int right = l - 1;
if(left <= right)
printf("%d %d\n", left, right);
else
printf("-1 -1\n");
}
int main(void)
{
scanf("%d%d", &n, &q);
for(int i = 0; i < n; ++i)
scanf("%d", &a[i]);
while(q--)
{
int tar;
scanf("%d", &tar);
Find(tar);
}
return 0;
}
题解：
记得找到一个临界点满足二分的判断。比如在 [1 2 2 3 3 4] 中找 3 ：
我们发现左端点的右侧严格小于 3，右端点的右侧严格大于 3
#include<cstdio>
const int N = 100010;
int n, q;
int a[N];
int main(void)
{
scanf("%d%d", &n, &q);
for(int i = 0; i < n; ++i)
scanf("%d", &a[i]);
for(int i = 0; i < q; ++i)
{
int m;
scanf("%d", &m);
// 计算左端点
int l = 0, r = n - 1;
while(l < r)
{
int mid = l + r >> 1;
if(a[mid] >= m) r = mid;
else l = mid + 1;
}
int left = l;
// 如果左端点不是 q 说明 q 不存在
if(a[l] == m)
{
r = n - 1;
while(l < r)
{
int mid = l + r + 1>> 1;
if(a[mid] <= m)
l = mid; // 如果 mid 给 l，那么计算 mid 时应该加 1
else r = mid - 1;
}
printf("%d %d\n", left, r);
}
else
{
printf("-1 -1\n");
}
}
return 0;
}
22. 旋转数组的最小数字
把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。
输入一个升序的数组的一个旋转，输出旋转数组的最小元素。
例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。
数组可能包含重复项。
注意：数组内所含元素非负，若数组大小为0，请返回-1。
样例
输入：nums=[2,2,2,0,1]
输出：0
class Solution {
public:
int findMin(vector<int>& nums)
{
int n = nums.size() - 1;
if(n < 0) return -1;
// 二分时以 nums[0] 为目标点
// [nums[0], target) 大于等于 nums[0]
// [target, nums[n]] 小于 nums[0]
// 但是这里存在一个问题，可能右区间存在等于 nums[0] 的元素，我们需要去除
// 比如：[1,2,3,0,1,1]
while(n > 0 && nums[n] == nums[0]) --n;
// 上面的过程可能会把右区间全部删除，比如 [1,2,3,1,1]
if(nums[n] >= nums[0]) return nums[0];
int l = 0, r = n;
while(l < r)
{
int mid = l + r >> 1;
if(nums[mid] < nums[0]) r = mid;
else l = mid + 1;
}
return nums[l];
}
};
113. 特殊排序
有N个元素，编号1.2..N，每一对元素之间的大小关系是确定的，关系具有反对称性，但不具有传递性。
注意：不存在两个元素大小相等的情况。
也就是说，元素的大小关系是N个点与N*(N-1)/2条有向边构成的任意有向图。
然而，这是一道交互式试题，这些关系不能一次性得知，你必须通过不超过10000次提问来获取信息，每次提问只能了解某两个元素之间的关系。
现在请你把这N个元素排成一行，使得每个元素都小于右边与它相邻的元素。
你可以通过我们预设的bool函数compare来获得两个元素之间的大小关系。
例如，编号为a和b的两个元素，如果元素a小于元素b,则compare（a,b）返回true，否则返回false。
将N个元素排好序后，把他们的编号以数组的形式输出，如果答案不唯一，则输出任意一个均可。
数据范围
1≤N≤1000
输入样例
[[0, 1, 0], [0, 0, 0], [1, 1, 0]]
输出样例
[3, 1, 2]
二分 + 插入排序
// Forward declaration of compare API.
// bool compare(int a, int b);
// return bool means whether a is less than b.
class Solution {
public:
vector<int> specialSort(int N) {
vector<int> res;
res.push_back(1);
for(int i = 2;i <= N;i++){
int l = 0,r = res.size() - 1;
// 找到的 l 为第一个大于 i 的元素的前一位
while(l < r){
int mid = l + r + 1 >> 1;
if(compare(res[mid],i)) l = mid;
else r = mid - 1;
}
res.push_back(i);
for(int j = res.size() - 2; j > r; j--) swap(res[j],res[j + 1]);
// 如果所有元素均大于 i ，再交换一次
if(compare(i, res[l])) swap(res[l], res[l + 1]);
}
return res;
}
};
上一道题的思路和下面一道题有关，我们可以看一下
162. 寻找峰值
峰值元素是指其值大于左右相邻值的元素。
给你一个输入数组 nums，找到峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，返回 任何一个峰值 所在位置即可。
你可以假设 nums[-1] = nums[n] = -∞ 。
示例 1：
输入：nums = [1,2,3,1]
输出：2
解释：3 是峰值元素，你的函数应该返回其索引 2。
示例 2：
输入：nums = [1,2,1,3,5,6,4]
输出：1 或 5
解释：你的函数可以返回索引 1，其峰值元素为 2；
或者返回索引 5， 其峰值元素为 6。
提示：
1 <= nums.length <= 1000
-231 <= nums[i] <= 231 - 1
对于所有有效的 i 都有 nums[i] != nums[i + 1]
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/find-peak-element 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。