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

本篇为学习笔记，学习视频为：二分查找 | 妈妈再也不怕我写错二分啦 | 五点七边二分视频补充_哔哩哔哩_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-砍树

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

二分答案是将所有结果集分为满足和不满足两部分，即求最小答案的最大值 or 最大答案的最小值时考虑

此题分类时一定注意是 要满足部分的最小值，也就是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：枚举答案，即枚举最小跳跃距离

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
 
int L, n, m;
const int N = 50010;
int nums[N];
 
//x为此时最小跳跃距离
bool check(int x) {
	int i = 0,j = 0;
	int cnt = 0;
	while(i < n + 1) {
		i++;
		if (nums[i] - nums[j] < x) {
			cnt++;
		}
		else {
			j = i;
		}
	}
	if (cnt > m) return false;
	else return true;
}
 
int main() {
	cin >> L >> n >> m;
	for (int i = 1; i <= n; i++) {
		cin >> nums[i];
	}
	nums[0] = 0;
	nums[n + 1] = L;
	int l = 0, r = L + 1;
	while (l + 1 != r) {
		int mid = (l + r) >> 1;
		if (check(mid)) l = mid;
		else r = mid;
	}
	if (check(l)) cout << l;
	else cout << r;
 
	return 0;
}

二分答案例题6：最大值最小-P路标设置

P3853 [TJOI2007] 路标设置 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

#include<iostream>
using namespace std;
 
int L, n, k;
const int N = 100010;
int nums[N];
int s[N];
 
bool check(int x) {
	int cnt = 0;
	for (int i = 1; i <= n; i++) {
		if (s[i] > x) {
			cnt++;
			int num = s[i] - x;
			while (num > x) {
				cnt++;
				num -= x;
			}
		}
		
	}
	if (cnt > k) return true;
	else return false;
}
 
//枚举路标的最大距离的最小值
int main() {
	cin >> L >> n >> k;
	for (int i = 1; i <= n; i++) {
		cin >> nums[i];
		s[i] = nums[i] - nums[i - 1];
	}
 
	int l = 0, r = L + 1;
	while (l + 1 != r) {
		int mid = (l + r) >> 1;
		if (check(mid)) l = mid;
		else r = mid;
	}
	if (!check(r)) cout << r;
	else cout << l;
 
	return  0;
}

浮点二分 - 求三次方根

给定一个浮点数 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;
}

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