学会二分法，有这一篇就够啦！
作者：blue
时间：2024.9
二分法是大家耳熟能详的基础算法，但是二分法，可没有你想像的那么简单，本篇将从二分法的两个经典利用场景——二分查找和二分答案，来讲懂二分法。
二分法应用在一串有序的序列中，查找一个我们所需要的值，注意一定是有序的序列。
比如说两个人玩猜数字游戏，1-10000，A心中想一个数，B来猜，B每次猜一个数，A都会回答他大了还是小了，这样B每次都可以折半的缩小查找的区间，这样就比直接把数从1数到10000要快很多。
1.二分查找
很多教学都让大家背二分法的模板，我不这样认为，因为二分法是一个非常好理解的算法，所以用不着背模板，而是要理解算法的过程知道代码是怎么写的，这样才能熟练的掌握二分法。
首先：二分法代码不能乱来，一定要根据你的区间来敲
我推荐的写法是根据左闭右闭区间的方法来写，下面是二分法的左闭右闭区间的代码
while(left<=right) //这里是你的循环条件,left<=right,这就意味着left和rigth都是包含在我们可取的一个范围之内
{
int mid=(left+right)/2; //那我们这里算出mid,如果mid的值不符合条件,那么mid就不应该包含在我们接下来我们
if(target else if(target>nums[mid]) left=mid+1;//我们的区间才符合我们设置的左闭右闭区间的规则 else return mid; } 再次强调：你进入while循环的条件一定要符合你的区间，也就是说你更新的区间一定要与你一开始查找的区间类型一致。 你一开始是[left,right]（左闭右闭），你更新完还得是左闭右闭；！！！ 有了固定好区间的思想，你在写二分法的时候，才不会搞不懂，到底是应该left<=right，还是left 接下来我们来看例题： 704. 二分查找 - 力扣（LeetCode） 这是二分查找的模板题，大家可以先点击链接自己做一遍再回来看我的代码。 我在这里给出了左闭右闭，和左闭右开区间的两种写法，如果对此前讲解有不理解的同学可以结合以下代码再体会以下。 左闭右闭： class Solution { public: int search(vector int left=0,right=nums.size()-1;//左闭右闭 while(left<=right) { int mid=(left+right)/2; if(target else if(target>nums[mid]) left=mid+1; else return mid; } return -1; } }; 左闭右开： class Solution { public: int search(vector int left=0,right=nums.size();//左闭右开，为什么这里是左闭右开，因为nums.size()是取不到的下标 while(left { int mid=(left+right)/2; if(target else if(target>nums[mid]) left=mid+1; else return mid; } return -1; } }; 如果你成功的用两种不同的区间，写出了这道题，那么恭喜你，搞明白了区间与while循环判断条件的关系，接下来就要看一些比较特殊的二分查找： 1.二分查找元素第一次出现的位置 由于我们查找的有序序列元素可能还是重复的，那我们应该如何去找第一个符合要求元素出现的位置呢？请看如下解释： 代码中用ans来表示查找到元素的位置，与原来二分查找不同的是，这里找到目标值后并不直接退出，而是你要找在这个已经找到的目标值的位置的左边还有没有target，所以用先ans记住这个位置，然后r=mid-1查找左边还有没有目标值，这样就可以找到元素第一次出现的值了。 int ans=-1; int l=1,r=n;//左闭右闭 while(l<=r) { int mid=(r+l)/2; if(a[mid] else if(a[mid]>target) r=mid-1; else if(a[mid]==target){ ans=mid; r=mid-1; } } cout< 2.二分查找元素最后一次出现的位置 查找元素最后一次出现的位置也很简单，那就是先用ans记住当前位置，然后l=mid+1 查找右边还有没有目标值，这样就可以找到元素最后一次出现的位置。 int ans=-1; scanf("%lld",&target); int l=1,r=n;//左闭右闭 while(l<=r) { int mid=(r+l)/2; if(a[mid] else if(a[mid]>target) r=mid-1; else if(a[mid]==target){ ans=mid; l=mid+1; } } cout< 以上的两个类型在后面有比较大的应用，请读者细细品味，掌握了再往下看 2.二分答案 其实二分答案和二分查找中找元素第一次出现的位置，和最后一次出现的位置的思想非常的像！ 它具有这种典型的特征：求...最大值的最小 、 求...最小值的最大 只要你搜索的答案是一个单调有序的区间。 我们直接通过例题来讲 P1873 [COCI 2011/2012 #5] EKO / 砍树 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 题目大意：让我们找到一个尽可能高的高度（因为这样砍的树少），然后得到至少等于M的木材 这题我们对答案（也就是砍树的高度）进行一个二分搜索（只要这个高度下所得到木材>=M,那他就是一个合法的高度），题目的要求是你找到一个符合条件的答案，并不是直接输出这个答案，而是让这个值尽量大，所以你找到在这道题中 ans>=m 都是符合条件的，所以你每找到一个符合条件的，就先把他记录下来，然后再往他的右边找，那就是 l=mid+1; #include using namespace std; using ll=long long; const int N=1e7+10; ll a[N]; int main() { ll n,m; cin>>n>>m;//M是目标木材数 ll ans=-1; ll l=0x3f3f3f3f,r=0; for(int i=1;i<=n;i++) //边输入边找左右区间，显然最小的高度是最矮的树，最大的高度是最高的树 { cin>>a[i]; l=min(l,a[i]); r=max(r,a[i]); } //左闭右闭 while(l<=r) { ll res=0; int mid=l+(r-l)/2;//防止爆int for(int i=1;i<=n;i++){ //算出这个高度下能获得的木材数 if(a[i]>mid) res+=(a[i]-mid); } if(res>=m){ //尽量高，所以要找符合的最后出现的位置 ，所以先用ans记录合法位置，再往右找看看能不能 ans=mid; //有更高的位置 l=mid+1; } else if(res //说明太高了，不够，那只能降低高度 r=mid-1; } } cout< return 0; } 再来一道题： P2440 木材加工 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 题目大意：把n根木头，切成k段，长为l的木头，使这个l尽量大 我们可以二分l的长度，看看合法的l中最长的是哪一个，详细看代码中的注释 #include #define int long long using namespace std; const int N=1e5+10; int a[N]; signed main() { int n,k; int ans=0; int l=1,r=0;//左区间l=1，题目中描述如果连 1cm 长的小段都切不出来，输出 0。 cin>>n>>k; //所以最后查找不到的话，就输出0即可 for(int i=1;i<=n;i++) { cin>>a[i]; r=max(a[i],r);//最长的段自然是只可能是最长的木材 } while(l<=r)//左闭右闭 { int res=0; int mid=l+(r-l)/2;//防止爆int，mid就是我们设置的切的段长 for(int i=1;i<=n;i++){ res+=a[i]/mid; //看看每根木头能切几段这样的木材 } if(res>=k){ //合法，看看能不能更长 ans=mid; l=mid+1; } else r=mid-1; //不合法，太长了，要短一点 } cout< return 0; } 恭喜你已经做到这里了，我们趁热打铁来看看两道竞赛真题，这两题都有非二分的做法，但我个人认为二分的做法更易于理解 0冶炼金属 - 蓝桥云课 (lanqiao.cn) 题目大意：炉子有一个称作转换率的属性 V，V 是一个正整数，这意味着消耗 V 个普通金属 O 恰好可以冶炼出一个特殊金属 X 现有N 条冶炼记录 每条记录中包含两个整数 A 和 B，这表示本次投入了 A 个普通金属 O，最终冶炼出了 B 个特殊金属 X。 （每条记录都是独立的，这意味着上一次没消耗完的普通金属 O 不会累加到下一次的冶炼当中。） 根据这 N 条冶炼记录，请你推测出转换率 V 的最小值和最大值 #include #define int long long using namespace std; const int N=1e4+10; int A[N],B[N]; signed main() { int n; int ans_min,ans_max; int MIN=0x3f3f3f3f;//上界 cin>>n; for(int i=1;i<=n;i++) { cin>>A[i]>>B[i]; MIN=min(MIN,A[i]/B[i]);//为什么我们要找一个最小的转换率来当右边界 } //因为如果你找的是一个最大的转换率，那么其他记录A个金属O,可能炼制不出B个金属X //但你找最小的，至少可以保证每条记录都是合法的 int l=1,r=MIN;//左闭右闭，找最小值，即符合要求后往左边找 while(l<=r) { int flag=1; int mid=l+(r-l)/2; for(int i=1;i<=n;i++)//检测mid这个转换率是否合格 { if((A[i]/mid)>B[i]) { flag=2;break;} //转换率太小当向右 else if((A[i]/mid) flag=3;break;}//转换率太大当向左 } if(flag==1){ ans_min=mid;r=mid-1;} else if(flag==2) { l=mid+1;} else if(flag==3) { r=mid-1;} } cout< //其实接下来这段代码可以不写，为什么，因为我们在一开始找右边界的时候，其实就已经找到了一个最大的，能让所有记录都合法的边界值了。 /*l=1;r=MIN; while(l<=r)//同理，找最大值 { int flag=1; int mid=l+(r-l)/2; for(int i=1;i<=n;i++) { if((A[i]/mid)>B[i]) {flag=2;break;} else if((A[i]/mid) } if(flag==1){ans_max=mid;l=mid+1;} else if(flag==2) {l=mid+1;} else if(flag==3) {r=mid-1;} } cout< cout< return 0; } 0卡片 - 蓝桥云课 (lanqiao.cn) 小蓝有 k 种卡片, 一个班有 n 位同学, 小蓝给每位同学发了两张卡片, 一 位同学的两张卡片可能是同一种, 也可能是不同种, 两张卡片没有顺序。没有 两位同学的卡片都是一样的。 给定 n, 请问小蓝的卡片至少有多少种? 根据题目，我们不难看出牌的种数可以组成的不同的方案为、 (1,1) (1,2) (1,3) (1,4) (1,5) (2,2) (2,3) (2,4) (2,5) (3,3) (3,4) (3,5) (4,4) (4,5) (5,5) 牌的种类，可以构成的牌组合的总数，其实是一个等差数列 比如说有3种牌 那就可以构成 [(1+3)*3]/2=6,6种不同的组合，就可以分给6位同学。 所以题目给定同学的数量，我们就找最少几种牌，构成的组合总数，可以容纳这些同学， 这样就把问题演变成了，查找最少种类牌，那就可以用到二分答案 #include #define int long long using namespace std; signed main() { int n; int ans; cin>>n; int l=1,r=1e9; while(l<=r) { int mid=(l+r)/2; int s=(mid+1)*mid/2; if(s>=n) { ans=mid;r=mid-1; } else l=mid+1; } cout< return 0; }