二分查找：万能模板及详细例题

本篇为学习笔记，学习视频为：二分查找 | 妈妈再也不怕我写错二分啦 | 五点七边二分视频补充_哔哩哔哩_bilibili

目录

        整数二分

万能模板：

做题步骤：

例题

二分查找例题1： 数的范围

二分查找例题2：A - B数对

二分答案例题3：P1873-砍树

二分答案例题4：P2440-木材加工

二分答案例题5：P2678-跳石头

浮点二分 - 求三次方根

        整数二分

万能模板：

int l = -1,r = N;
    while(l + 1 != r){
        int mid = l + r >> 1;
        if(isBlue(mid)) l = mid;
        else r = mid;
    }

isBlue是一个判断函数，最后停止时，l 指蓝色的最后一个数，r指红色的第一个数，两者相邻且有一个看不见的分界线，如下图：

​

做题步骤：

• 写出 isBlue 函数
• 判断最后返回应该是l还是r
• 套模板

​

例题

二分查找例题1： 数的范围

给定一个按照升序排列的长度为 n 的整数数组，以及 q 个查询。

对于每个查询，返回一个元素 k 的起始位置和终止位置（位置从 0 开始计数）。

如果数组中不存在该元素，则返回 -1 -1。

要找到x的起始位置和结束位置，也就是要找到第一个不<x和最后一个不> x

• 起始位置：isBlue : < x, return r  
• 结束位置：isBlue ：<= x,return l  

#include<iostream>
using namespace std;

const int N = 100010;
int nums[N];
int n,q;

int main(){
    cin >> n >> q;
    for(int i = 0;i < n;i++) cin >> nums[i];
    
    for(int i = 0;i < q;i++){
        int x;
        cin >> x;
        int l = -1,r = n;
        while(l + 1 != r){
            int mid =( l + r )>> 1;
            if(nums[mid] < x) l = mid;
            else r = mid;
        }
        if(nums[r] != x)    cout << "-1 -1" << endl;
        else{
            cout << r << " ";
             l = -1,r = n;
            while(l + 1 != r){
                int mid =( l + r )>> 1;
                if(nums[mid]  <=  x) l = mid;
                else r = mid;
            }
            cout << l << endl;
        }
        
    }
    
    return 0;
}

二分查找例题2：A - B数对

https://www.luogu.com.cn/problem/P1102

给出一串正整数数列以及一个正整数 C，要求计算出所有满足 A−B=C 的数对的个数（不同位置的数字一样的数对算不同的数对）。

 思路：转换为A = B + C，枚举B，然后在数组中找A是否存在 

注意：int： 2的30次方  long long：2的60次方，因此count需要开long long

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

int n,c;
const int N = 200010;
int nums[N];

int bsearch1(int x){
    int l = -1,r = n;
    while(l + 1 != r){
        int mid = (l + r) >> 1;
        if(nums[mid] <  x) l = mid;
        else r = mid;
    }
    if(nums[r] == x)  return r;
    else return -1;
}

int bsearch2(int x){
    int l = -1,r = n;
    while(l + 1 != r){
        int mid = ( l + r) >> 1;
        if(nums[mid] <= x) l = mid;
        else r = mid;
    }
    if(nums[l] == x )  return l;
    else return -1;
}

int main(){
    cin >> n >> c;
    long long count = 0;
    
    for(int i = 0;i < n;i++) cin >> nums[i];
    sort(nums,nums + n);
    
    for(int b = 0;b < n;b++){
        int b1 = bsearch1(nums[b] + c);
        if(b1 != -1){
            int b2 =  bsearch2(nums[b] + c);
            count += b2 - b1 + 1;
        }
        
    }
   cout << count;
    return 0;
}

二分答案例题3：P1873-砍树

二分答案是将所有结果集分为满足和不满足两部分，此题分类时一定注意是 要满足部分的最小值，也就是res>=m返回l ，而不要想着要求m

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

int n, m;
const int N = 1000010;
int nums[N];

bool check(int x){
    int res = 0;
     for (int i = 0; i < n; i++) {
        if (nums[i] - x > 0) {
            res += nums[i] - x;
        }
        if(res >= m) return true;
    }
     return false;
}

//至少得到M米
int main() {
    cin >> n >> m;
    int maxh = 0;
    for (int i = 0; i < n; i++) {
        cin >> nums[i];
        maxh = max(nums[i], maxh);
    }

    int l = 0,r = maxh + 1;
    while(l + 1 != r){
        int mid = (l + r) >> 1;
        if(check(mid)) l = mid;
        else r = mid;
    }
    if(check(r)) cout << r << endl;
    else cout << l << endl;
    
    return 0;
}

二分答案例题4：P2440-木材加工

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

将木头按长度l切，使所有的木头切完后可以正好有k段，l越大越好，因此本题应该从l出发，枚举每种l的可能，找到恰好是不满足题意的那个点

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

int n, k;
const int N = 100010;
int nums[N];

bool check(int x){
    int ans = 0;
    for(int i = 0;i < n;i++){
        ans += nums[i] / x;
         if(ans >= k) return true;
    }
   
    return false;
}

int main() {
    cin >> n >> k;
    int longest = 0;
    for(int i = 0;i < n;i++){
        cin >> nums[i];
        longest = max(longest,nums[i]);
    } 
    
    int l = 0,r = longest + 1;
    while(l + 1 != r){
        int mid = (l + r) >> 1;
        if(check(mid)) l = mid;
        else r = mid;
    }
    
    if(check(r)) cout << r << endl;
    else cout << l << endl;
    
    return 0;
}

二分答案例题5：P2678-跳石头

P2678 [NOIP2015 提高组] 跳石头 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

 方法1：枚举搬走哪块石头，但选择太多，一定会超时

方法2：枚举答案，即枚举最小跳跃距离，

浮点二分 - 求三次方根

给定一个浮点数 n，求它的三次方根。

#include<iostream>
using namespace std;

int main(){
    double x;
    cin >> x;
    
    double l = -100,r = 100;
    
    while(r - l > 1e-8){
        double mid = (l + r) /2;
        if(mid * mid * mid <= x) l = mid;
        else r = mid;
    }
    printf("%.6f",l);
    return 0;
}

优化一下，可以直接二分一百次来求结果：

#include<iostream>
using namespace std;

int main(){
    double x;
    cin >> x;
    
    double l = -100,r = 100;
    
    for(int i = 0;i < 100;i++){
        double mid = (l + r) /2;
        if(mid * mid * mid <= x) l = mid;
        else r = mid;
    }
    printf("%.6f",l);
    return 0;
}

以上是本文全部内容，如果对你有帮助点个赞再走吧~  ₍˄·͈༝·͈˄*₎◞ ̑̑