---
title: "二分相关模型"
created: 2025-11-28
tags:
  - 算法
---

# 二分相关模型

## 感悟

感觉难点主要在要想到是否能用二分去写

很多题目在看过讲解后才恍然大悟原来这也能二分

但自己看的话 怎么都不觉得可以二分

这个东西emm可能是不熟练导致的

反正照这几道题看来

现在已经有点眉目了

对于一些有单调性的题目 （结果一定满足某一边满足某一边不满足）

比如最大最小解啊什么的 这种很明显看得出来了

（发现这些题目都是在问一些 最大是多少 最小是多少 这类的）

有个灵感就是

尝试把这个答案当成已知的

把区间划分成两段 答案不一定非得在左半边 也可能在右半边

（在左边找的是最大 在右边找的是最小）

然后去任取一个满足条件的mid

看它要满足什么条件才能是在这个答案区间里面 即check函数怎么写

然后再根据mid在答案的左边还是右边

去进行范围缩小 移动l、r指针

——**把不太好做的找最优解的问题转变成判定性的问题 一直套答案 不是就再猜一个答案**

可以直接用库函数lower_bound( ）代替手写二分

lower_bound( )和upper_bound( )都是利用二分查找的方法在一个排好序的数组中进行查找的。

在从小到大的排序数组中

lower_bound( begin,end,num)：从数组的begin位置到end-1位置二分查找第一个大于或等于num的数字，找到返回该数字的地址，不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。

upper_bound( begin,end,num)：从数组的begin位置到end-1位置二分查找第一个大于num的数字，找到返回该数字的地址，不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。

在从大到小的排序数组中，重载lower_bound()和upper_bound()

lower_bound( begin,end,num,greater() ):从数组的begin位置到end-1位置二分查找第一个小于或等于num的数字，找到返回该数字的地址，不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。

upper_bound( begin,end,num,greater() ):从数组的begin位置到end-1位置二分查找第一个小于num的数字，找到返回该数字的地址，不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。

// 升序数组中：

upper_bound(a.begin(), a.end(), x); // 查找第一个 > x的元素

lower_bound(a.begin(), a.end(), x); // 查找第一个 >= x的元素

// 降序数组中：

upper_bound(a.begin(), a.end(), x, greater()); // 查找第一个 < x的元素

lower_bound(a.begin(), a.end(), x, greater()); // 查找第一个 <= x的元素

比如 在二分模板题可以写成：

```cpp
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'

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

int SL(int l,int r,int k){
	while(l<r){
		int m=l+r>>1;
		if(nums[m]>=k)
			r=m;
		else
			l=m+1;
	}
	return r;
}

int SR(int l,int r,int k){
	while(l<r){
		int m=l+r+1>>1;
		if(nums[m]<=k)
			l=m;
		else
			r=m-1;
	}
	return r;
}

int main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>q;
    for(int i=0;i<n;i++)
        cin>>nums[i];

    while(q--){
       	int k; cin>>k;

		//int l=SL(0,n-1,k);;
        int l=lower_bound(nums,nums+n,k)-nums;

        if(nums[l]!=k)
            cout<<"-1 -1"<<endl;
        else{
            cout<<l<<" ";
            // int r=SR(0,n-1,k);
            int r= upper_bound(nums,nums+n,k)-nums-1;

            cout<<r<<endl;
        }
    }
    return 0;
}
```

![[image-395d97af.png]]

对于答案在右边的情况 可以用lower_bound()直接找

注意点为：lower_bound()返回的是指针 把它再减去数组首地址（数组名）即可得到答案下标

然后第一个参数是数组开始 第二个参数是数组结尾 第三个参数为要找的值

所以最终写成lower_bound(nums,nums+n,k)-nums;

对于答案在左边的情况 可以用upper_bound()的结果再减去1得到

因为它找到的是第一个不满足的 那么满足的就在该位置的左边

所以写成upper_bound(nums,nums+n,k)-nums-1;

只能用在很明显的要去找一个数的情况下

如果要比较复杂的check逻辑

就不能用库函数代替

而且 库函数效率要比手写二分慢一点点

所以 没啥用的小技巧……

## 题集

二分往往与其他基础算法相结合 其实下面的题都是有一定难度的 很锻炼思维

先来几道板子题及简单变形试试水

- [[sqrt(x)|sqrt(x)]]
- [[有效完美平方|有效完美平方]]
- [[排列硬币|排列硬币]]
- [[分巧克力|分巧克力]]

结合前缀和、双指针、差分、离散化等基础算法：

- [[2-Learning/02-算法/03-刷题理模型/二分相关模型/餐厅|餐厅]]
- [[2-Learning/02-算法/03-刷题理模型/二分相关模型/借教室|借教室]]
- [[2-Learning/02-算法/03-刷题理模型/二分相关模型/最佳牛围栏|最佳牛围栏]]
- [[2-Learning/02-算法/03-刷题理模型/二分相关模型/赶牛入圈|赶牛入圈]]

结合数学知识：

- [[2-Learning/02-算法/03-刷题理模型/二分相关模型/3、冶炼金属|3、冶炼金属]]
- [[剪绳子|剪绳子]]

结合单调栈（构造二段性）：

- [[2-Learning/02-算法/03-刷题理模型/二分相关模型/最长连续子序列|最长连续子序列]]

经典 影响范围模型 按标的顺序刷

1、[[农田灌溉|农田灌溉]]

2、[[学生和导师|学生和导师]]
3、[[2-Learning/02-算法/03-刷题理模型/二分相关模型/倒垃圾|倒垃圾]]
4、[[2-Learning/02-算法/03-刷题理模型/二分相关模型/无线网络|无线网络]]

5、[[2-Learning/02-算法/03-刷题理模型/二分相关模型/管道|管道]]

二分找影响范围 如何判断影响返回合法 可以暴力遍历、区间合并 可以二分找最近 双指针找最近

感兴趣可以把这些题目都用4种方法写一下 再琢磨一下什么情况用什么方法

把上面的题刷懂了就差不多了 后面再碰到二分整理在下面

- [[2-Learning/02-算法/03-刷题理模型/二分相关模型/5、四平方和|5、四平方和]]
- [[机器人跳跃问题|机器人跳跃问题]]

- [[2-Learning/02-算法/03-刷题理模型/二分相关模型/卡牌|卡牌]]
- [[2-Learning/02-算法/03-刷题理模型/二分相关模型/5、递增三元组|5、递增三元组]]

- [[小蓝与数轴|小蓝与数轴]]
- [[小蓝与捉迷藏|小蓝与捉迷藏]]
- [[小蓝与换装大赛|小蓝与换装大赛]]

- [[愤怒的牛|愤怒的牛]]
- [[楼梯|楼梯]]
- [[爱吃香蕉的珂珂|爱吃香蕉的珂珂]]

- [[分配给商店的最多商品的最小值|分配给商店的最多商品的最小值]]

**更多题目：**

辅导课

- [机器人跳跃问题](https://www.acwing.com/problem/content/732/)
- [四平方和](https://www.acwing.com/problem/content/1223/)
- [分巧克力](https://www.acwing.com/problem/content/1229/)
- [特殊排序](https://www.acwing.com/problem/content/115/)
- [防线](https://www.acwing.com/problem/content/122/)

- [x 的平方根](https://leetcode.com/problems/sqrtx/) [csdn](https://blog.csdn.net/WhereIsHeroFrom/article/details/119976200)
- [有效的完全平方数](https://leetcode.com/problems/valid-perfect-square/description/)
- [排列硬币](https://blog.csdn.net/WhereIsHeroFrom/article/details/119976202)
- [第一个错误的版本](https://blog.csdn.net/WhereIsHeroFrom/article/details/118453857)
- [H 指数 II](https://leetcode-cn.com/problems/h-index-ii/)
- [乘法表中第k小的数](https://leetcode-cn.com/problems/kth-smallest-number-in-multiplication-table/)

- [二分查找](https://blog.csdn.net/WhereIsHeroFrom/article/details/118445716)
- [剑指 Offer 53 - I. 在排序数组中查找数字 I](https://blog.csdn.net/WhereIsHeroFrom/article/details/120754826)
- [在排序数组中查找元素的第一个和最后一个位置](https://blog.csdn.net/WhereIsHeroFrom/article/details/120754826)
- [寻找比目标字母大的最小字母](https://blog.csdn.net/WhereIsHeroFrom/article/details/118452682)
- [搜索插入位置](https://blog.csdn.net/WhereIsHeroFrom/article/details/118452682)
- [剑指 Offer II 068. 查找插入位置](https://blog.csdn.net/WhereIsHeroFrom/article/details/120754826)
- [区间内查询数字的频率](https://blog.csdn.net/WhereIsHeroFrom/article/details/123932685)
- [统计「优美子数组」](https://blog.csdn.net/WhereIsHeroFrom/article/details/119976203)
- [两数之和 II - 输入有序数组](https://blog.csdn.net/WhereIsHeroFrom/article/details/118507985)
- [剑指 Offer II 006. 排序数组中两个数字之和](https://blog.csdn.net/WhereIsHeroFrom/article/details/118507985)
- [和为s的两个数字](https://blog.csdn.net/WhereIsHeroFrom/article/details/118507985)
- [两数之和](https://blog.csdn.net/WhereIsHeroFrom/article/details/118507985)
- [统计有序矩阵中的负数](https://leetcode-cn.com/problems/count-negative-numbers-in-a-sorted-matrix/)
- [检查整数及其两倍数是否存在](https://blog.csdn.net/WhereIsHeroFrom/article/details/120754546)
- [排序矩阵查找](https://leetcode-cn.com/problems/count-negative-numbers-in-a-sorted-matrix/)
- [采购方案](https://blog.csdn.net/WhereIsHeroFrom/article/details/120754418)
- [早餐组合](https://leetcode-cn.com/problems/2vYnGI/)
- [交换和](https://blog.csdn.net/WhereIsHeroFrom/article/details/119976199)
- [分割数组的最大值](https://leetcode-cn.com/problems/split-array-largest-sum/)
- [找出给定方程的正整数解](https://leetcode-cn.com/problems/find-positive-integer-solution-for-a-given-equation/)
- [比较字符串最小字母出现频次](https://leetcode-cn.com/problems/compare-strings-by-frequency-of-the-smallest-character/)
- [同时运行 N 台电脑的最长时间](https://leetcode.cn/problems/maximum-running-time-of-n-computers/)

- [丑数 III](https://leetcode-cn.com/problems/ugly-number-iii/)
- [第 k 个缺失的正整数](https://blog.csdn.net/WhereIsHeroFrom/article/details/120756312)
- [尽可能使字符串相等](https://leetcode-cn.com/problems/get-equal-substrings-within-budget/)
- [制作 m 束花所需的最少天数](https://leetcode-cn.com/problems/maximum-fruits-harvested-after-at-most-k-steps/)
- [最大连续1的个数 III](https://leetcode-cn.com/problems/max-consecutive-ones-iii/)
- [水位上升的泳池中游泳](https://leetcode-cn.com/problems/swim-in-rising-water/)
- [剑指 Offer II 073. 狒狒吃香蕉](https://leetcode-cn.com/problems/nZZqjQ/)
- [每个小孩最多能分到多少糖果](https://blog.csdn.net/WhereIsHeroFrom/article/details/123935689?spm=1001.2014.3001.5501)
- [爱吃香蕉的珂珂](https://leetcode-cn.com/problems/koko-eating-bananas/)
- [分配给商店的最多商品的最小值](https://blog.csdn.net/WhereIsHeroFrom/article/details/123964006)
- [花园的最大总美丽值](https://leetcode.cn/problems/maximum-total-beauty-of-the-gardens/description/)
- [找出第 k 小的距离对](https://blog.csdn.net/WhereIsHeroFrom/article/details/124076264)

---
⬅️ [[sqrt(x)|sqrt(x)]] 🏠 [[00-刷题理模型]] ➡️ [[2-Learning/02-算法/03-刷题理模型/二分相关模型/倒垃圾|倒垃圾]]