学会二分法，有这一篇就够啦！

作者：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<nums[mid]) right=mid-1;//循环的区间中，所以应该是mid-1或mid+1，这样才能将mid排除在区间之外
    else if(target>nums[mid]) left=mid+1;//我们的区间才符合我们设置的左闭右闭区间的规则
    else return mid;
 }

再次强调：你进入while循环的条件一定要符合你的区间，也就是说你更新的区间一定要与你一开始查找的区间类型一致。

你一开始是[left,right]（左闭右闭），你更新完还得是左闭右闭；！！！

有了固定好区间的思想，你在写二分法的时候，才不会搞不懂，到底是应该left<=right，还是left<right，其实都是可以的，只是后者是左闭右开区间，对应的区间变化，也应该符合左闭右开区间的规则。

接下来我们来看例题：

704. 二分查找 - 力扣（LeetCode）

这是二分查找的模板题，大家可以先点击链接自己做一遍再回来看我的代码。

我在这里给出了左闭右闭，和左闭右开区间的两种写法，如果对此前讲解有不理解的同学可以结合以下代码再体会以下。

左闭右闭：

class Solution {
   
public:
    int search(vector<int>& nums, int target) {
   
        int left=0,right=nums.size()-1;//左闭右闭
        while(left<=right)
        {
   
            int mid=(left+right)/2;
            if(target<nums[mid]) right=mid-1;
            else if(target>nums[mid]) left=mid+1;
            else return mid;
        }
        return -1;
    }
};

左闭右开：

class Solution {
   
public:
    int search(vector<int>& nums, int target) {
   
        int left=0,right=nums.size();//左闭右开，为什么这里是左闭右开，因为nums.size()是取不到的下标
        while(left<right) 
        {
   
            int mid=(left+right)/2;
            if(target<nums[mid]) right=mid; //由于是左闭右开，所以mid可以包含在开区间中，不用mid-1
            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]<target) l=mid+1;
    else if(a[mid]>target) r=mid-1;
    else if(a[mid]==target){
        ans=mid;
        r=mid-1;
    }
}
cout<<ans<<" ";

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]<target) l=mid+1;
    else if(a[mid]>target) r=mid-1;
    else if(a[mid]==target){
   
        ans=mid;
        l=mid+1;
    }
}
cout<<ans<<" ";

以上的两个类型在后面有比较大的应用，请读者细细品味，掌握了再往下看

2.二分答案

其实二分答案和二分查找中找元素第一次出现的位置，和最后一次出现的位置的思想非常的像！

它具有这种典型的特征：求...最大值的最小 、 求...最小值的最大

只要你搜索的答案是一个单调有序的区间。

我们直接通过例题来讲

P1873 [COCI 2011/2012 #5] EKO / 砍树 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

题目大意：让我们找到一个尽可能高的高度（因为这样砍的树少），然后得到至少等于M的木材

这题我们对答案（也就是砍树的高度）进行一个二分搜索（只要这个高度下所得到木材>=M,那他就是一个合法的高度），题目的要求是你找到一个符合条件的答案，并不是直接输出这个答案，而是让这个值尽量大，所以你找到在这道题中 ans>=m 都是符合条件的，所以你每找到一个符合条件的，就先把他记录下来，然后再往他的右边找，那就是 l=mid+1;

#include <iostream>
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<m){
    //说明太高了，不够，那只能降低高度
            r=mid-1;
        }
    }
    cout<<ans;
    return 0;
}

再来一道题：

P2440 木材加工 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

题目大意：把n根木头，切成k段，长为l的木头，使这个l尽量大

我们可以二分l的长度，看看合法的l中最长的是哪一个，详细看代码中的注释

#include <iostream>
#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<<ans;
    return 0;
}

恭喜你已经做到这里了，我们趁热打铁来看看两道竞赛真题，这两题都有非二分的做法，但我个人认为二分的做法更易于理解

0冶炼金属 - 蓝桥云课 (lanqiao.cn)

题目大意：炉子有一个称作转换率的属性 V，V 是一个正整数，这意味着消耗 V 个普通金属 O 恰好可以冶炼出一个特殊金属 X

现有N 条冶炼记录

每条记录中包含两个整数 A 和 B，这表示本次投入了 A 个普通金属 O，最终冶炼出了 B 个特殊金属 X。

（每条记录都是独立的，这意味着上一次没消耗完的普通金属 O 不会累加到下一次的冶炼当中。）

根据这 N 条冶炼记录，请你推测出转换率 V 的最小值和最大值

#include <iostream>
#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)<B[i]) {
   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<<ans_min<<" ";
  //其实接下来这段代码可以不写，为什么，因为我们在一开始找右边界的时候，其实就已经找到了一个最大的，能让所有记录都合法的边界值了。
  /*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)<B[i]) {flag=3;break;}
    }
    if(flag==1){ans_max=mid;l=mid+1;}
    else if(flag==2) {l=mid+1;}
    else if(flag==3) {r=mid-1;}
  }
  cout<<ans_max<<" ";*/
  cout<<MIN;
  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 <iostream>
#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<<ans;
  return 0;
}