概念解释

概述

二分法在算法竞赛中一般有这么一个用途：在一个具有单调性的解空间中找到符合题意的一个可行解。下面解释几个专有名词：

解空间

很简单，就是可能存在解的逻辑区域。这个在算法入门时应提到。

可行解

符合题意的解

单调性

与数学中的基本是一回事。

算法分析

原理

就是数学中的逼近原理。通过计算机的高效计算，可以逐步靠近可行解；又由于解空间具有单调性，所以可以简化枚举的过程。简单来讲，二分是一种更高效的枚举手段。

应用

我们主要是研究在整数域上的二分。

1.二分查找

在一个序列中查找某一个指定的元素，这可以通过二分查找来实现。下面给出一个例子：

给出一个整数序列 $A$ ，这个序列有 $n$ 个元素。下有 $m$ 次询问，每次会询问一个整数，请回答该数是否在 $A$ 中。如果否，请分别输出大于或等于该数的第一个后继，小于或等于该数的第一个前驱以及-1；如果这个数存在，输出以上除-1之外并输出这个数。

这很显然如果朴素去求，时间复杂度会是 $O(mn)$ 的，在1e5及以上的规模下会TLE。下面考虑二分求解。

回忆概念，我们强调，要在一个单调的解空间中寻找答案。所以考虑对这个序列排序；时间复杂度为 $O(nlogn)$ 。然后执行以下过程：

将区间一分为二；
维护区间的中间端点 $mid$ 。记录 $a[mid]$ 的值。
如果 $a[mid]\leq x$ ，收缩左端点，重复以上步骤；
如果 $a[mid]\geq x$ ，收缩右端点，重复以上步骤；
直到区间被收缩至只有一个元素，检查这个元素是否是所求。

过程很简单，时间复杂度也很低，为 $O(log_{2}n)$ 。但是这里有很多的细节需要注意，笔者尽量把这些细节全部展示清楚。首先可以先看下面的参考程序，这里选择结合代码研究。

取等问题

很简单，总结出来就一句话：如果 $A$ 中的元素跟 $x$ 有可能取等，那么收缩区间时，区间端点与 $mid$ 就取等；反之，不能取等（这时往往+1或者-1）。也就是相邻，一边是实心端点，一边是空心端点。还可以这么看：如果取等，意味着 $mid$ 处有可能会是答案，所以收缩区间时，区间端点可以等于 $mid$ 。

划分问题

也就是考虑 $mid$ 的取值。通常有两种：

$mid=(l+r)>>1$

以及

$mid=(l+r+1)>>1$

区别是：

第一种的写法不会取到 $r$ ，第二种写法不会取到 $l$ 。进一步地，我们知道，第一种是向下取整，称为左中位数；第二种向上取整，则是右中位数。我们可以利用这一性质处理无解的问题：设置最初区间分别为： $[0,n]$ 和 $[1,n+1]$ 把一个越界的下标包括起来，如果最后停止在这个下标上，说明无解。当然，第一种适用于找后继，第二种适用于找前驱。

STL 函数

下面介绍两个 STL 的函数，分别是 lower_bound()，upper_bound()。这两个函数分别返回的是在一个单调递增序列中第一个大于或等于某个数的后继，以及第一个大于某数的后继。同样在下面给出手写代码。这里的关键就是上面说的划分问题。

2.二分答案

这里主要是两类问题，最大值最小化以及最小值最大化。也就是判定问题。我们一开始就说过，

“ 通过计算机的高效计算，可以逐步靠近可行解；又由于解空间具有单调性，所以可以简化枚举的过程。简单来讲，二分是一种更高效的枚举手段。”

所以归根结底还是二分查找。请记住：最优化问题往往等价于一个可行性问题的判定。进一步地，是在一个具有严格约束的情况下利用二分法枚举出一个答案来。

这句话非常有信息量。我们会给出几个等价的表述以及几个例子深刻去理解。

有这么几种表述：

建立一个定义域为解空间，值域为0或1的单调分段函数，在这个函数上二分查找分界点。

其实本质都是一回事。

下面给出几个例子理解一下。

最小值最大化

例题：luogu.P2678 [NOIP 2015 提高组] 跳石头

二分所求。找出约束：

“由于预算限制，组委会至多从起点和终点之间移走 M 块岩石（不能移走起点和终点的岩石）。”

也就是说，M 是约束。这样就容易设计 $check$ 函数：每次枚举一个最小值，检查是否合法。由于这个最小值是具有单调性的，所以可以考虑二分出这个最大值。

最大值最小化

例题：luogu.P3853 [TJOI2007] 路标设置

二分所求。找出约束：

“以及最多可增设的路标数量”

也就是说，路标数量是约束。这样就容易设计 $check$ 函数：每次枚举一个最大值，检查是否合法。由于这个最大值是具有单调性的，所以可以考虑二分出这个最小值。

参考程序

在单调递增序列中查找 $\geq x$ 的最小的元素

//
while(l<r)
{int mid=(l+r)>>1;if(a[mid]<=x) l=mid;else r=mid-1;
} 
return a[l];//a[l]==a[r]为终止条件

在单调递增序列中查找 $\leq x$ 的最小的元素

//
while(l<r)
{int mid=(l+r+1)>>1;if(a[mid]>=x) r=mid;else l=mid-1;
} 
return a[l];//a[l]==a[r]为终止条件

最小值最大化

//
#include<iostream>
using namespace std;
int d[50005];
int l,n,m;
bool check(int k)//我们要二分的是最短跳跃距离
{int last=0,ans=0;for(int i=1;i<=n+1;i++){if(d[last]+k>d[i]) ans++;else last=i;}return ans<=m;//是否满足约束
}
int main()
{cin>>l>>n>>m;for(int i=1;i<=n;i++)cin>>d[i];d[n+1]=l;int le=0,ri=l*2;while(le<ri)//二分{int mid=(le+ri+1)>>1;if(check(mid)) le=mid;else ri=mid-1;}cout<<le;return 0;
}

最大值最小化

//
#include<cstdio>
using namespace std;
int d[100005];
int l,n,k;
bool check(int w)//现在就假设我这里的w就是最大值 
{int last=0,ans=0;for(int i=2;i<=n;i++){//while(d[i]>last+w) last+=w,ans++;//我们二分已经是最大距离，如果有比这还大的，那就是要增设 //last=d[i];ans+=(d[i]-d[i-1]-1)/w;}return ans<=k;
}
int main()
{ scanf("%d%d%d",&l,&n,&k);for(int i=1;i<=n;i++)scanf("%d",&d[i]);int le=1,ri=l;while(le<ri){int mid=(le+ri)>>1;if(check(mid)) ri=mid;else le=mid+1;}printf("%d",le);return 0;
}