二分的性质
若一组数有单调性则一定可以二分，但可以二分的题目不一定有单调性（有单调性则一定可以二分，没有单调性也有可能可以二分）
二分的本质(边界)：若给定一组数据在这组数据上定义了某种性质，使得这个性质若在右半边满足则左半边一定不满足则可以使用二分
整数二分
代码模板
//区间[l, r]被划分成[l, mid]和[mid + 1, r]时使用 模板1
int bsearch_1(int l, int r)
{
while (l < r)
{
int mid = (l + r) / 2;
if (check(mid)) r = mid; // check()判断mid是否满足性质
else l = mid + 1;
}
return l;
}
-----------------------------------------------------------------------------------------
// 区间[l, r]被划分成[l, mid - 1]和[mid, r]时使用 模板2
int bsearch_2(int l, int r)
{
while (l < r)
{
int mid = (l + r + 1) / 2;
if (check(mid)) l = mid;
else r = mid - 1;
}
return l;
}
注(模板2）：当l = r-1时及l和r只差一的时候若mid = (l + r) / 2代入特殊值l = 1,r = 2则mid = (1+2)/2 = 1则mid = l区间没变进入死循环
例题： 0到n-1中缺失的数字
题目描述
一个长度为 n−1n−1 的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围 00 到 n−1n−1 之内。在范围 00 到 n−1n−1 的 nn 个数字中有且只有一个数字不在该数组中，请找出这个数字。
数据范围： 1≤ n ≤1000
样例
输入：[0,1,2,4]
输出：3
算法分析
通过上述样例可以看出缺失数字左面的数字和下标相同，而缺失数字右面的数字和小标不同，而且区间[l, r]可以通过是否下标等于对应数字被划分成[l, mid]和[mid + 1, r]，所有使用模板1。另外要注意特殊情况：当所有数都满足nums[i] == i时，表示缺失的是 n。
C代码
int getMissingNumber(int* nums, int numsSize) {
int l = 0, r = numsSize - 1, mid ;
if(numsSize == 0) return 0;
while( l < r)
{
mid = l + r >> 1;
if(mid == nums[mid])
l = mid + 1;
else
r = mid;
}
if(nums[r]== r) r++;
return r;
}
浮点数二分
代码模板
double bsearch_3(double l, double r)
{
while (r - l > 1e-6)
{
double mid = (l + r) / 2;
if (check(mid)) r = mid;
else l = mid;
}
return l;
}
注：1e-6表示计算精度，一般题目若要求精确至小数点后4位用1e-6，及精确至小数点后n位用1e-(n+2)
例题： 剪绳子
题目描述
有 N 根绳子，第 3 根绳子长度为 L₃，现在需要 M 根等长的绳子，你可以对 N 根绳子进行任意裁剪（不能拼接），请你帮忙计算出这 M 根绳子最长的长度是多少。
数据范围
1≤N,M≤100000,
0<Li<10^9
输入格式
第一行包含 2 个正整数 N、M，表示原始绳子的数量和需求绳子的数量。
第二行包含 N 个整数，其中第 i 个整数 Li 表示第 i 根绳子的长度。
样例
3 4
3 5 4
输出格式
输出一个数字，表示裁剪后最长的长度，保留两位小数。
样例
2.50
样例解释
第一根和第三根分别裁剪出一根 2.50 长度的绳子，第二根剪成 2 根 2.50 长度的绳子，刚好 4 根。
算法分析
因为0<Li<10^9所有另l=0 r=1e9则mid = (l + r) / 2定义一个函数判断按照长度为mid截取是否可以截取够需求的数量，若可以则证明mid左面的数均可以所以令l=mid用来判断右面的数以求出最优解；反之则证明mid右面的数均不满足，另令r=mid用来继续判断左面以找出满足的解。
C代码
#include<stdio.h>
int a[100010];
int n , m ;
int panduan(double mid)
{
int num=0 , i;
for(i = 0 ; i < n ; i ++)
num += a[i] / mid;
int t=0;
if(num >= m) t = 1 ;
return t;
}
main()
{
int i;
scanf("%d%d",&n,&m);
for(i = 0 ; i < n ; i ++)
scanf("%d",&a[i]);
double l = 0 , r = 1e9 , mid ;
while(r -l > 1e-4)
{
mid = (l + r) / 2 ;
if(panduan(mid))
l = mid;
else
r = mid;
}
printf("%.2f",l);
}
参考内容
AcWing 常用代码模板1——基础算法
AcWing 680. 剪绳子-视频讲解
AcWing 68. 0到n-1中缺失的数字 - 题解
网友评论