【算法题解】二分查找的经典问题解析
什么是二分？
二分是一种思想，用于有序数组中快速查找目标元素。
用动图展示一下二分查找：
二分查找的模版很简单，但是很多题目很难想到用二分。
关于二分的一些题目
1.分巧克力
题目描述：
圈出来的都是重要信息。
这道题的大致意思就是有N个小朋友，现在有K个蛋糕，这K个蛋糕，蛋糕的长和宽都给出，现在要切蛋糕，但是蛋糕必须满足一定条件，保证边长是整数，并且保证切出来的蛋糕都是一样的并且是正方形（输入的蛋糕必须保证每个小朋友都可以分到1*1的蛋糕）。
用上面的样例举例：
第一种满足要求的切法：
如果我们再增加到33就不满足了。
可以看到增加到33后最多可以切4个，已经不满足条件了。
所以这个例子的最大的边长就是2.
解题思路
首先，先看看这道题问的什么，这道题问的是输出可以切出来的正方形的最大边长。
这道题叫我们求边长，他问什么我们就二分什么。
这道题我们就二分边长，这道题已经给出了边长的范围了。
所以这道题我们应该将边的范围限制在这个范围中间，l就是1，r就是1e5，在这个范围进行二分。
那么区间我们已经划定好了，区间变换的条件是什么呢？
我们假设我们第一次二分，这个数是满足的，如果这个数是满足的，那么答案是在左边还是右边呢？很显然是在右边，因为这道题求的是最大值，如果当前的数满足左边的比当前数小的数肯定都满足，但是最佳答案肯定是当前数，所以左边的数可以不做考虑了，所以下一次二分的区间应该是当前数到r。
那么如果当前数不满足反过来肯定是要缩小范围，所以下一次二分的区间应该是l到当前数。
那么具体条件是什么呢？
题目已经给出了满足的条件了，我们只需要编写一个函数检查一下这个边长是否满足当前条件即可。
很显然，就是要求每个蛋糕切出来的蛋糕总数大于等于总人数。
即：
t
o
t
a
l
=
(
h
[
i
]
/
e
d
g
e
)
∗
(
w
[
i
]
/
e
d
g
e
)
>
=
k
total=(h[i]/edge)*(w[i]/edge)>=k
total=(h[i]/edge)∗(w[i]/edge)>=k
上面total就是一个for循环的事。
编写代码
#include<iostream>
using namespace std;
const int N=1e5+10;
//巧克力个数和人数
int n,k;
// 长 宽
int h[N],w[N];
bool check(int num)
{
//记录巧克力的个数
int count=0;
for(int i=0;i<n;i++)
{
//累加第i个巧克力分成成的小巧克力
count+=(h[i]/num)*(w[i]/num);
}
if(count>=k)return true;
return false;
}
int main()
{
cin>>n>>k;
for(int i=0;i<n;i++)cin>>h[i]>>w[i];
int l=1,r=1e5;
//进行二分
while(l<r)
{
//向上取整
int mid=l+(r-l+1>>1);
if(check(mid)) l=mid;
else r=mid-1;
}
//输出巧克力的边长
cout<<r<<endl;
return 0;
}
2.数组中数值和下标相等的元素
题目描述：
这道题就是一个很常规的二分模版题。
编写代码：
class Solution {
public:
int getNumberSameAsIndex(vector<int>& nums) {
int l=0,r=nums.size()-1;
while(l<=r)
{
//找到中间数下标
int mid=(l+r+1)/2;
if(mid>nums[mid]) l=mid;
else if(mid<nums[mid]) r=mid-1;
else return nums[mid];
}
return -1;
}
};
3.0到n-1中缺失的数字
题目描述：
这道题也是一个很常规的二分题。
class Solution {
public:
int getMissingNumber(vector<int>& nums) {
if(nums.size()==0)return 0;
if(nums.size()==1)return 1;
int l=0,r=nums.size()-1;
while(l<r)
{
int mid=(l+r+1)/2;
if(mid==nums[mid])l=mid;
else if(mid<nums[mid])r=mid-1;
}
if(nums[r]!=r)return r;
else return r+1;
}
};
4.数列分段 II
题目描述：
这道题的意思就和很简单，给定一个长度为N个数组，让我们将这个数组分为M段，因为有很多种分法，所以每个分法的每段中肯定能选出最大值，所以这道题的意思就是让我们求出所有分法中的最大值的最小值。
解题思路
这道题还是延续我们第一道题的想法，这道题求的是每个每种分法的最大值的最小值，所以我们对最大值进行二分，首先我们来确定二分的范围，由于是求分段的和，所以这个和肯定不可能比这数组中最大的还小，所以二分的下限肯定是数组中的数的最小值。二分的上限是数组的和（不可能你一个段的和比整个数组的和还大吧）
二分的区间已经确定了，应该确定二分的条件了，利用一点点贪心从第一个位置开始顺序的进行分段，用一个sum来维护这个段的和，用一个seg来维护段数。
如果当前段的和加上下一个即将入段的数小于等于需要二分的数的话，就将这个数入段，如果大于大于当前的数，那么就开辟新的段，这里的开辟新的段只需要将seg++，然后将sum置为下一个数即可，最后看分出的段是否小于给定的段数，如果小于的话说明成立，则返回true，如果大于的话说明不成立，直接返回false。(为什么只需要小于，因为如果小于的话，指定的段数是肯定能补足的）
如果成立的话说明还有比这个数更小的数，则下一次二分二分的区间就是l到当前数。
如果不成立的话说明这个数足够小了，没有满足的即二分的区间是当前数到r。
编写代码
#include<iostream>
using namespace std;
const int N=1e5+10;
int n,m,a[N];
bool check(int num)
{
int seg=0,sum=0;
for(int i=0;i<n;i++)
{
if(sum+a[i]<=num) sum+=a[i];
else
{
sum=a[i];
seg++;
}
}
return seg<m;
}
int main()
{
cin>>n>>m;
int l=0,r=0;
for(int i=0;i<n;i++)
{
cin>>a[i];
l=max(l,a[i]);
r+=a[i];
}
while(l<r)
{
int mid=(l+r)/2;
if(check(mid))r=mid;
else l=mid+1;
}
cout<<l<<endl;
return 0;
}
总结
二分查找不仅是一种高效的算法，更是一种通用的解题思想。它通过每次将问题规模减半，显著提高了查找效率，尤其适用于有序数据或可以通过特定条件划分搜索空间的问题。在实际编程中，熟练掌握二分查找的应用场景和技巧，不仅能帮助解决许多算法题，还能拓宽你对算法优化的思考维度。因此，深入理解二分的原理，并善于在各种场景中运用它，是提升算法能力的重要一步。
原文地址：https://blog.csdn.net/2301_79969994/article/details/142985350
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！