二分

二分法

二分查找(Binary Search),也叫折半查找,是用来在一个有序数组中查找某一元素的算法。

原理

以在一个升序数组中查找一个数为例。

它每次考察数组当前部分的中间元素,如果中间元素刚好是要找的,就结束搜索过程;如果中间元素小于所查找的值,那么左侧的只会更小,不会有所查找的元素,只需到右侧查找;如果中间元素大于所查找的值同理,只需到左侧查找。

性质

最优时间复杂度 O(1)O(1) 平均与最坏时间复杂度 O(logn)O(\log n)
空间复杂度:递归版 O(logn)O(\log n) 递归版(一般使用 while 循环实现) O(1)O(1)

实现

迭代版

1
2
3
4
5
6
7
8
9
10
11
12
13
int binarySearch(int target){
int l=0,r=n-1;
while(l<r){
int mid=(l+r)>>1,x=arr[mid];//在有符号整数中 >>1 往往比 /2 更加快速
if(x<target){
l = mid+1;
}else{
r = mid;
}
}
if(arr[l]==target) return l;
return -1;
}

STL

STL提供了以下三种二分查找函数:

TIPS:加"[ ]"的是可选参数

binary_search(start,end,target,[compare]):在 [start,end)[start,end) 的范围内寻找 targettarget ,找到返回 truetrue 否则返回 falsefalse

upper_bound(start,end,target,[compare])
[start,end)[start,end) 的范围内寻找最后一个 targettarget ,找到返回最后一个 targettarget地址,否则返回 endend

lower_bound(start,end,target,[compare])
[start,end)[start,end) 的范围内寻找第一个 targettarget ,找到返回第一个 targettarget地址,否则返回 endend

如:

listlist = {1,2,2,2,4,5,7,8,9,9,9}

方法查找值结果(为了方便,直接返回下标)
binary_search2true
upper_bound23
lower_bound21

其他

前文提到的"有序数组"的"有序"是广义的,如果一个数组中的左侧或者右侧都满足某一种条件,而另一侧都不满足这种条件,也可以看作是一种有序(如果把满足条件看做 11 ,不满足看做 00 ,至少对于这个条件的这一维度是有序的)。换言之,二分搜索法可以用来查找满足某种条件的最大(最小)的值。

二分答案

解题的时候往往会考虑枚举答案然后检验枚举的值是否正确。若满足单调性,则满足使用二分法的条件。把这里的枚举换成二分,就变成了“二分答案”。

二分答案的步骤:

  1. 确认题目能否使用二分答案(一般是求最小中的最大,最大中的最小)
  2. 确定二分枚举的值(如P1182中每段和的最大值)
  3. 写出check函数(检验函数),一般使用贪心等方法
  4. 套用二分查找模板

例题

P1542 包裹快递

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
题目描述
K成功地破解了密文。但是乘车到X国的时候,发现钱包被偷了,于是无奈之下只好作快递员来攒足路费去Orz教主……

一个快递公司要将n个包裹分别送到n个地方,并分配给邮递员小K一个事先设定好的路线,小K需要开车按照路线给的地点顺序相继送达,且不能遗漏一个地点。小K得到每个地方可以签收的时间段,并且也知道路线中一个地方到下一个地方的距离。若到达某一个地方的时间早于可以签收的时间段,则必须在这个地方停留至可以签收,但不能晚于签收的时间段,可以认为签收的过程是瞬间完成的。

为了节省燃料,小K希望在全部送达的情况下,车的最大速度越小越好,就找到了你给他设计一种方案,并求出车的最大速度最小是多少。

输入格式
1行为一个正整数n,表示需要运送包裹的地点数。

下面n行,第i+1行有3个正整数xiyisi,表示按路线顺序给出第i个地点签收包裹的时间段为[xi, yi],即最早为距出发时刻xi,最晚为距出发时刻yi,从前一个地点到达第i个地点距离为si,且保证路线中xi递增。

可以认为s1为出发的地方到第1个地点的距离,且出发时刻为0

输出格式
仅包括一个正数,为车的最大速度最小值,结果保留两位小数。

先读题,发现是求"最大速度最小值",明显的二分答案。我们要枚举的值明显也是这个最小的最大速度。
根据题意,可写出判断函数:

1
2
3
4
5
6
7
8
9
bool check(long double x){//x为当前枚举出的速度
long double time=0;//注意精度 time为当前时间
for(int i=0;i<n;i++){
time += datas[i].dist / x;//距离除以速度等于时间
if(time>datas[i].end) return false;//如果来晚了就无法完成
if(time<datas[i].start) time = datas[i].start;//如果来早了可以等到可签收时间段
}
return true;//送出所有包裹,答案可行
}

再写出二分模板:

1
2
3
4
5
6
7
8
9
while(r-l>=1e-5){//保证精度,不漏掉可能的答案(直接l<=r或l<r可能会死循环)
long double mid = (l+r)/2;//注意:浮点数不能使用>>1除以2
if(check(mid)){
r = mid;//如果当前答案可行(时间充裕)就往小枚举速度
ans = mid;//保存最优解
}else{
l = mid;//否则往大枚举速度(送的太慢需要增加速度)
}
}

完整代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <algorithm>
#include <iostream>
#include <iomanip>
using namespace std;
struct Data{//结构体存放地点
int start,end,dist;
};
Data datas[200010];
int n;
long double l,r=1e9,ans;//设置r的时候不要超过有效范围
bool check(long double x){
long double time=0;
for(int i=0;i<n;i++){
time += datas[i].dist / x;
if(time>datas[i].end) return false;
if(time<datas[i].start) time = datas[i].start;
}
return true;
}
int main(){
cin >> n;
for(int i=0;i<n;i++){
cin >> datas[i].start >> datas[i].end >> datas[i].dist;
}
while(r-l>=1e-5){
long double mid = (l+r)/2;
if(check(mid)){
r = mid;
ans = mid;
}else{
l = mid;
}
}
cout << fixed << setprecision(2) << ans << endl;//注意精度要求
return 0;
}

本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!