Skip to main content

二分查找与二分搜索

二分查找​

查找​

tip

直接使用c++ stl的lower_bound 函数求解即可；

#include <iostream>
#include<algorithm>
using namespace std;

const int N = 1e6 + 10;
int a[N];
int n,m;

int main()
{
    cin >> n >> m;
    for (int i = 0; i < n; i ++ )
        cin >> a[i];

    for(int i = 0;i < m;i++)
    {
        int x;
        cin >> x;
        int p = lower_bound(a,a + n,x)-a+1;
        if(a[p-1] == x)
            cout << p << ' ';
        else 
            cout << -1 << ' ';
    }    
}

A-B 数对​

tip

stl大法好，具体的题目请看原文

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

const int N = 2e5 + 10;

LL a[N];
int cnt[N];
LL n,c;
LL res;

int main()
{
    // freopen("1.txt","r",stdin);
    cin >> n >> c;
    for(int i = 0;i < n;i++) cin >> a[i];
    sort(a, a + n);
    for(int i = 0;i < n;i++)
    {
        if(a[i] < c) continue;
        if(a[i] == a[i-1])
        {
            res += cnt[i-1];
            cnt[i] = cnt[i-1];
            continue;
        }
        int p = lower_bound(a,a + i,a[i] - c) - a;
        while(a[p++] == a[i] - c) cnt[i]++;
        res += cnt[i];
    }
    cout << res;
    return 0;
}

烦人的高考支援​

tip

使用二分算法找到第一个大于a的值, 注意需要设置一下开头和结尾，否则会产生错误结果

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;
long long scores[N],n,m,ans;

int main()
{
    // freopen("1.txt","r",stdin);
    cin >> n >> m;
    for(int i = 1;i <= n;i++) cin >> scores[i];
    sort(scores+1,scores+n+1);
    scores[0]=-1e12;scores[n+1]=1e12;   
    while(m--)
    {
        int s;
        cin >> s;
        int p = lower_bound(scores + 1,scores + n + 1,s) - scores;
        ans += min(abs(scores[p] - s), abs(s - scores[p - 1]));
    }
    cout << ans;
}

银行贷款​

tip

浮点数二分

#include<bits/stdc++.h>
using namespace std;

int sum,t,mon;
double sumt;

int check(double mid)
{
    sumt=sum;
    for(int i=1;i<=mon;i++){
        sumt=sumt+sumt*mid-t;
    }
    if(sumt>=0) return 1;
    return 0;
} 

int main(){
    cin>>sum>>t>>mon;
    
    double l=0,r=500; //答案范围尽量开大些
    while(r-l>1e-5) //精度保证 
    {
        double mid=(l+r)/2;
        if(check(mid)) r=mid;   //如果最后还不完了，说明利率高了   
        else l=mid;
    }
    printf("%.1f",l*100);
    return 0;
}

数的范围​

tip

二分查找n组查询

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1e6 + 10;
int num[N];
int n,m;

int main()
{
    cin >> n >> m;
    for (int i = 0; i < n; i ++ ) cin >> num[i];
    while (m -- ){
        int x;
        cin >> x;
        int l = lower_bound(num,num+n,x) - num;
        if(num[l] != x) 
        {
            cout << -1 << " " << -1 << endl;
            continue;
        }else{
            int r = upper_bound(num,num+n,x) - num - 1;
            cout << l << " " << r << endl;
        }
    }
}

二分答案​

tip

什么时候用二分答案？

  1. 答案在一个区间内（一般情况下，区间会很大，暴力超时）
  2. 直接搜索不好搜，但是容易判断一个答案可行不可行
  3. 该区间对题目具有单调性，即：在区间中的值越大或越小，题目中的某个量对应增加或减少。

典型特征：求...最大值的最小、...最小值的最大

tip

这一类题目的关键点：

  1. 判断是求最大值的最小还是求最小值的最大
  2. 判断二分的初始l和人
  3. 写好check函数的返回条件，想好什么时候返回

木材加工​

tip

首先我们判断一下，答案肯定在一个区间里面，且答案是具有单调性的（每段木头的长度越长切割出来的段数就越短）。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

const int N = 1e5 + 10;
LL n,m,maxa;
LL a[N];

bool check(LL mid)
{
    LL sum = 0;
    for(int i = 0;i < n;i++)
        sum += (a[i] / mid);
    if(sum >= m) return true; // 得到的段数大于需要的段数->l=mid;
    else return false; // 得到的段数小于需要的段数->r=mid-1;
}

int main()
{
    // freopen("1.txt","r",stdin);
    memset(a,0,sizeof a);
    cin >> n >> m;
    LL sum = 0;
    for(int i = 0;i < n;i++) cin >> a[i],maxa = max(maxa,a[i]),sum+=a[i];
    int l = 0, r = maxa;
    if(sum < m){ // 判断是否有解
        cout << 0;
        return 0;
    }
    while(l < r)
    {
        LL mid = l + r + 1 >> 1;
        if(check(mid)) l = mid; 
        else r = mid - 1;
    }
    cout << l;
    return 0;
}

跳石头​

tip

拿的石头越多肯定两个石头之间的最短距离越大，我们可以用二分的思想来枚举最短距离，通过最短距离反过来推拿走的石头个数是不是符合要求的。

丢瓶盖​

tip

关键点：使得距离最近的瓶子距离最大，也就是在最小里面选最大的问题

思路：通过二分的方式去枚举距离最近瓶子的最大距离，check的思路就是看看当前这个距离能不能选取够m个瓶子。如果选不够说明距离太大了 r = mid-1, 如果选多了说明距离还可以变大 l = mid

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;
int n,m;
int a[N];
int maxa = -1e9,mina = 1e9;

bool check(int mid)
{
    int cnt = 1;
    for(int i = 0,j = 1;j < n;j++)
        if(a[j] - a[i] >= mid) 
            cnt++,i = j;
    
    // 注意拿的瓶子越多，瓶子之间的距离就可能越小
    if(cnt >= m) return true;
    else return false;
}

int main()
{
    // freopen("1.txt","r",stdin);
    cin >> n >> m;
    for(int i = 0;i < n;i++) cin >> a[i],maxa = max(a[i],maxa);
    int l = 0, r = maxa;
    sort(a,a + n);
    while(l < r)
    {
        int mid = l + r + 1 >> 1;
        if(check(mid)) l = mid;
        else r = mid-1;
    }
    cout << l;
}

数列分段 Section II​

tip

二分最终的是思想，能不能想起来用二分的方式去解决很重要。而且二分的题目很多都是反过来求解的，比如这题就是去枚举每段和最大值的最小值，然后去判断这个最大值能分成几段，根据段数进行二分； 

#include <bits/stdc++.h>
using namespace std;

const int N  = 1e8 + 10;
int n,m;
int a[N];
int maxa;

bool check(long long mid)
{
    int cnt = 0;
    long long sum = 0;
    for(int j = 0;j < n-1;j++)
    {
        sum += a[j];
        if(sum + a[j+1] > mid) cnt++,sum=0;
    }
    // 分段个数越多，每段的和就越大
    // 我们的目标是让每段的最大值最小
    if(cnt + 1 <= m) return 1; 
    else return 0; 
}

int main()
{
    // freopen("1.txt","r",stdin);
    cin >> n >> m;
    long long sum = 0;
    for (int i = 0; i < n; i ++ ) cin >> a[i],sum += a[i],maxa = max(maxa,a[i]);
    // 最小是maxa，最大是sum
    long long l = maxa, r = sum;
    while(l < r)
    {
        int mid = (l + r) >> 1;
        if(check(mid)) r = mid;
        else l = mid + 1;
    }
    cout << l;
}

参考资料​

[1] https://blog.csdn.net/Mr_dimple/article/details/114656142