本文共 2640 字，大约阅读时间需要 8 分钟。

写在前面

最近在刷二分的题目顺带总结一下，如果有不懂的欢迎在下面留言和评论。二分可以和哈希，数论，dp，各种结合，二分只是一个思想并非一个模板。

二分查找

二分查找的速度非常之快，时间复杂度为O(logn) ，也就是如果在有序的2^31规模的数据里找一个数字，只需要31次即可找到。

二分的应用

二分在竞赛之中常常用来去解决线性答案的问题，通过二分去搜索答案。

竞赛选手常常使用STL来解决二分的问题 最常用的是upper_bound 和 lower_bound 内部实现的代码如下：

二分的基础练习

1、解方程

链接：https://ac.nowcoder.com/acm/problem/14416

通过二分降低数据时间复杂度。

题目分析

首先对题目进行分析，已知x，从数列里找到3个数字，代入方程式满足等式。

如果用一般的三层循环for 或者dfs ，时间复杂度为O(n^3),很明显这个不符合本题的条件。 所以我们可以用二分的思维去降低时间复杂度，如何做呢？ 我们对等式分析，我们可以先两重循环遍历a和b 算出ax^2 + bx=-c ，然后我们再通过二分查找来找到c，如果找的到，那么就说明YES符合题意。（当然前提必须得排序）

时间复杂度分析

1.排序O(n*logn)

2.双重循环遍历O(n^2) 3.二分查找O(logn)

所以总时间复杂度为O(n^2)

题目数据量1e3 ，明显此算法行得通。

代码

#include
   
    using namespace  std;typedef long long ll;const ll N = 31625;const ll Mod = 1000000009;int a[1004];int main(){
   	int n, x;	cin >> n >> x;	for (int i = 0; i < n; i++)	{
   		cin >> a[i];	}	sort(a, a + n);	for (int i = 0; i < n; i++)	{
   		for (int j = 0; j < n; j++)		{
   			int c = (a[i] * x * x + a[j] * x);			int p =  lower_bound(a, a + n, -c)-a;			if (p >= 0 && p < n && a[p]+c==0)//如果p有效			{
   				cout << "YES";				return 0;			}		}	}	cout << "NO";}
   

2、不等式

链接：https://ac.nowcoder.com/acm/problem/14696

题目分析：首先对题目进行分析，首先我们得明白我们的求的是什么？ 求的是n！！！假设这个n为16，我们如何去计算x^3 * y <=n 有多少个解？

解法：我们可以写一个循环去遍历尝试x的值（x^3<=n），由题意我们从2开始，8*y<=16 化简一下 y<=2 也就是说 如果当x=2的时候，y的解有2个。

（我们选择增长快的x遍历去求n是一个好技巧） 所以解的个数的算法就出来了，我们设解的个数为cnt ，根据y=n/x^3 即 cnt+= n / x^3 (for 循环 x^3<=n)

for (ll x = 2; x*x*x <= n; x++)	{
   		cnt += n/(x*x*x);//y解的个数	}

很明显，n和m成正比例关系,只有n越多，m的解才能越多，所以我们于要求的n，是线性关系。

线性关系求最大值？？？ 当然是二分呀 ！

判断二分域m最小值是1，m越大n越大，所以n最小是8

我们的左区间l=8, 右区间为1e16(取个大的）

然后二分出答案就可以了，但是记得得在cnt==m时 特判一下，做一个标记或者去更新ans。这是为什么呢？看图

因为我们是不断去取最小值的过程，当符合条件了 我们一定得记录下来，表明我们找的到符合条件的。

#include
   
    using namespace  std;typedef long long ll;#define IOS ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)const ll INF = 0x3f3f3f3f3f3f3f3f;const ll N = 100000+5;const ll Mod = 1000000009;const ll MX = 0x3f3f3f3f;ll l = 1, r = 1e16 +1;ll  m;ll judge(ll n){
   	ll cnt = 0;	for (ll x = 2; x*x*x <= n; x++)	{
   		cnt += n/(x*x*x);//y解的个数	}	return cnt;}int main(){
   	IOS;	while (cin >> m)	{
   		l =8, r = INF		ll ans = -1;		while (l <= r)		{
   			ll mid = (l + r) >> 1;			ll cnt = judge(mid);			if (cnt>=m)			{
   				r = mid - 1;				if (cnt == m)					ans = mid;			}			else			{
   				l = mid + 1;			}		}		cout << ans << endl;	}	return 0;}
   

3、还是解方程

题目链接：https://ac.nowcoder.com/acm/problem/15717

首先我们看等式左边，明显的是单调递增函数，那么我们去二分y的值，就能轻松得到答案了。 但是这题唯一的难点在于，如何去解决这个精度的问题？ 1.如果两个浮点数小于1e-6,那么可以认为是相同。 2.我们用循环100次，去不断的逼近精度。（推荐）

还有，如何判定这个根本不存在？ 非常的简单，只要看左或右区间是否极限于左右边界即可

if (l == 100 || l == 0)//无限逼近左右两边说明不存在		{
   			printf("-1\n");		}

下面是ac的代码。

转载地址：http://fnjvz.baihongyu.com/