二分算法
二分算法
基本介绍
二分查找算法（Binary Search）是一种高效的查找算法，特别适用于在有序数组或列表中快速定位目标元素。它利用了分治法的思想，每次查找都将搜索范围缩小一半，因此时间复杂度为 O(log n)，效率非常高。
应用场景
有序数组查找
二分查找主要用于查找有序数组或列表中的目标元素。比如在一个按升序排列的整数列表中查找某个数字的索引位置。这种操作在数据库、字典等大量使用有序数据的场景中非常常见。
确定数值范围
在很多场景下，我们会面临需要找到某个数值的最小或最大满足条件的位置，比如最小值、最大值，或是满足某种条件的阈值。通过二分查找可以快速定位。例如：
找到大于等于某个数的最小位置。
lower_bound ( v.begin() , v.end() , x );
返回第一个大于等于x的迭代器，如果不存在，则返回 v.end() .
找到大于某个数的最小位置。
upper_bound ( v.begin() , v.end() , x );
返回第一个大于x的迭代器，如果不存在，则返回 v.end() .
解决搜索范围缩小的问题
在解决搜索范围不断缩小的问题时，二分查找也经常被用到。例如在查找一个旋转有序数组中的最小值、寻找峰值元素、判断是否存在重复元素等问题中，二分查找可以极大提升效率。
维护某种特性，二分迅速定位分界点
在某些问题中需要维护某种特性，若存在一点满足：该点之前的所有点都不满足这种特性，该点及之后的所有点都满足这种特性，则我们可以通过二分快速找到这个点。
例题
进击的奶牛
题目链接：进击的奶牛
题目描述
Farmer John 建造了一个有 N N N（ 2 ≤ N ≤ 1 0 5 2 \leq N \leq 10 ^ 5 2≤N≤105) 个隔间的牛棚，这些隔间分布在一条直线上，坐标是 x 1 , x 2 , ⋯ , x N x _ 1, x _ 2, \cdots, x _ N x1,x2,⋯,xN（ 0 ≤ x i ≤ 1 0 9 0 \leq x _ i \leq 10 ^ 9 0≤xi≤109）。
他的 C C C（ 2 ≤ C ≤ N 2 \leq C \leq N 2≤C≤N）头牛不满于隔间的位置分布，它们为牛棚里其他的牛的存在而愤怒。为了防止牛之间的互相打斗，Farmer John 想把这些牛安置在指定的隔间，所有牛中相邻两头的最近距离越大越好。那么，这个最大的最近距离是多少呢？
思路： 要找最大的最近距离，设为d。很容易推出最近距离比 d 小（大于0）的全都都满足牛之间不会互打，而最近距离比 d 大的都不满足，所以我们可以二分。具体看代码注释吧。
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 2e5 + 9;
int n,c,a[N];
bool check(int mid)
{
//cnt记录当前放了多少牛进牛棚
//idx记录当前牛所在的牛棚的下标
//初始都为 1
int cnt=1,idx=1;
while(idx<=n)
{
//lower_bound() 函数返回第一个大于等于a[idx]+mid
//更新idx
idx=lower_bound(a+1,a+1+n,a[idx]+mid)-a;
//如果idx > n 说明没有大于等于a[idx]+mid的值
//如果idx <= n 直接将一头牛放在编号为a[idx]的牛棚里
if(idx<=n) cnt++;
//cnt = c 时所有牛都放进牛棚中了，所以牛之间不会互打，满足条件，返回true
if(cnt==c) return true;
}
//不满足条件 返回false
return false;
}
void solve()
{
cin>>n>>c;//输入数据
for(int i=1;i<=n;i++) cin>>a[i];
//二分的前提：数据要有序
sort(a+1,a+1+n);
//定义左右边界，表示最近距离d
int l=0,r=1e9+1;
while(l+1!=r)//循环限制
{
int mid=(l+r)>>1;
//检查是否满足牛之间是否会互打
//不会互打，将范围缩至[mid,r]
//会互打，则将范围缩至[l,mid]
if(check(mid)) l=mid;
else r=mid;
}
//上述转换是l始终是满足牛之间不会互打的
cout<<l<<'\n';
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int _ = 1;
//cin >> _;
while (_--) solve();
return 0;
}
小红打怪
题目链接: 小红打怪
题目描述
有 n n n个怪物排成一排，小红和队友们准备进攻这些怪物。
小红的技能是全体打击，对所有怪物造成1点伤害。
队友1的技能是单体打击，对单体怪物造成1点伤害。
队友2的技能是范围攻击，对相邻的两只怪物分别造成1点伤害（可以对死去的怪物尸体释放该技能）。
每回合每个人均可释放1次技能。小红想知道，击杀全部怪物最少需要多少回合？
思路： 显然如果 x 回合能击杀所有的怪物，那么x+1，x+2，…，回合都行。所以答案满足单调性，即存在一个 x，使得小于 x 回合无法击败，大于等于 x 可以击败，所以我们可以二分。
那么难点来了，如何判断能否击败所有怪物
判断方法： 假设有 x 个回合，则小红攻击 x 次，队友1攻击 x 次，队友2攻击 x 次。小红是全体攻击直接将所有怪物的血量减少 x 即可。再考虑队友1和队友2，如果有两个相邻的怪物则队友2先攻击min( a[ i ] , a[ i+1 ] ) 次，剩下的再由队友1来攻击。
思路明确了，写代码吧
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 2e5 + 9;
int n,a[N],b[N];
//判断函数
bool check(int mid)
{
//x为队友1剩余的攻击次数
//y为队友2剩余的攻击次数
int x=mid,y=mid;
//执行小红的所有攻击、
//b数组记录本次判断的怪物的血量情况
for(int i=1;i<=n;i++) b[i]=max(0,a[i]-mid);
//从头到尾遍历，看能否击败所有怪物
for(int i=1;i<=n;i++)
{
//b[i]=0 说明这个怪物已经被击败了，跳过这个怪物
if(b[i]==0) continue;
//如果有活着的相邻两个怪物，优先考虑队友2攻击
if(b[i]&&b[i+1]&&y)
{
//队友2需要攻击mi次
int mi=min(b[i],b[i+1]);
if(y>=mi)//如果队友2的攻击次数大于等于mi直接攻击即可
{
y-=mi;
b[i]-=mi;b[i+1]-=mi;
}
else //队友2的攻击次数小于mi次，则使用完所有的攻击次数，剩下的交给队友1
{
b[i]-=y;b[i+1]-=y;
y=0;
}
}
if(x>=b[i])//队友1的攻击次数能击败当前怪物
{
x-=b[i];
b[i]=0;
}
else if(x+y>=b[i]) //队友1的攻击不足以击败当前怪物，但加上队友2能击败
{
y-=b[i]-x;
x=0;
b[i]=0;
}
else return false;//当前怪物无法击败，返回false
}
//击败了所有怪物，返回true
return true;
}
void solve()
{
//定义左右边界
int l=1,r=0;
//输入数据
cin>>n;
//有边界定义为 a数组 的最大值
for(int i=1;i<=n;i++) cin>>a[i],r=max(r,a[i]);
//二分
while(l+1!=r)
{
int mid=(l+r)>>1;
//判断是否能把所有怪物击败
if(check(mid)) r=mid;
else l=mid;
}
cout<<r<<'\n';
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int _ = 1;
//cin >> _;
while (_--) solve();
return 0;
}
总结
- 有序性：二分算法要求数据集合必须是有序的。
- 边界条件：需要特别注意循环条件和边界值的处理，以避免无限循环或数组越界。
- 对于非整数类型的数组，需要定义合适的比较规则。
二分查找是一种简单、高效的查找算法，但也有一定的适用范围。掌握二分查找的基础用法、扩展变种以及在不同场景中的应用，对于提升编程效率和优化算法有重要帮助。
标签：二分,int,基础,mid,算法,查找,队友,怪物 From： https://blog.csdn.net/2301_80487295/article/details/143660456