二分查找

发表于 分类于

二分查找版本众多，其中初始值的选择，判断条件，边界修改方式都有所不同。取整方式有向上取整和向下取整两种，区间开闭有左闭右开，左闭右闭，左开右闭，左闭右闭四种，再根据实际问题分为上界和下界两种，其中涉及细节繁多。在学习数据结构的时候讨论了不同版本平均查找长度和不同版本的正确性问题，但是仅限于三种版本，本文将讨论不同条件下二分查找的写法。

求下界

给定长度为$n$的单调不下降子序列$a_0,a_1,…,a_{n-1}$和一个数$k$,求满足$a_i\geq k$条件的最小的$i$

挑战程序设计竞赛中给出的二分查找算法如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int a[maxn];
int binsearch(int k){
    //初始化解存在的范围
    int lb=-1,ub=n;
    while(ub-lb>1){
        int mid=(lb+ub)/2;
        if(a[mid]>=k){
            ub=mid;
            //解的范围变为(lb,mid]
        }
        else{
            lb=mid;
            //解的范围变为(mid,ub]
        }
    }
    return ub;
}

binsearch(int k)在存在满足条件的$a_i$时返回对应数组下标的值，在不存在的时候返回$n$。

初始化解中$ub=n$，$n$不在数组下标索引范围内，用于在查找失败时候返回$n$。若序列$a_0,a_1,…,a_{n-1}$中不存在满足$a_i\geq k$的$i$，即$a_i<k$对$i=0,1,..,n-1$均满足，每次迭代选择$lb=mid$分支，直到搜索区间缩减为$(n-1,n]$。

接下来讨论每次迭代时边界的修改，根据$a[mid]$与$k$的相对大小

  • $a[mid]\geq k$,$mid$点满足$a[mid]\geq k$,所求为满足条件的最小下标，故大于$mid$的部分均可以舍去。在该情况下右边界可以取到，所以取$ub=mid$,此时解的范围为$(lb,mid]$

  • $a[mid]<k$,$mid$不可能为解，左边界不可以取到，所以取$lb=mid$,此时解的范围为$(mid,ub]$

    每次迭代的时候满足$a_i \geq k$的最小下标必然还存在于区间内

循环在满足$ub-lb>1$的时候执行，即在$ub-lb\leq1$的时候停止执行，$(lb，ub]$此时仅有$a[ub]$一个元素。若序列$a_0,a_1,…,a_{n-1}$存在满足$a_i\leq k$的$i$,则必然为$ub$,否则为$n$。

c++标准库中中lower_bound()等价于以下形式：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int lower_bound(int k){
    int first=0,last=n;
    //区间为[0,n)
    while(first<last){
        int mid=first+(last-first)/2;
        if(a[mid]>=k){
            last=mid;
        }
        else{
            first=mid+1;
        }
    }
    return first;
}

lower_bound()在序列$a_0,a_1,…,a_{n-1}$存在满足$a_i\leq k$的$i$时返回$n$。

这里的mid写法和挑战程序设计竞赛上不一样，防止了在相加时的溢出问题。

1
mid=(first+last)/2=(2*first+last-first)/2=first+length/2

二者在算术意义上是等价的。

将问题中的$\geq$更改为$>$，得到以下问题：

给定长度为$n$的单调不下降子序列$a_0,a_1,…,a_{n-1}$和一个数$k$,求满足$a_i> k$条件的最小的$i$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int upper_bound(int first,int last,int value){
    int first=0,last=n;
    //区间为[0,n)
    while(first<last){
        int mid=first+(last-first)/2;
        if(a[mid]>k){
            last=mid;
        }
        else{
            first=mid+1;
        }
    }
    return first;
}

与lower_bound()类似，upper_bound()在序列$a_0,a_1,…,a_{n-1}$不存在满足$a_i <k$的$i$时返回$n$。

实际算法题往往是求满足条件的最小值，一般用以下形式：

1
2
3
4
5
6
7
8
9
10
11
int search(int low, int high) {
  int ans = -1;
  while (low <= high) {
    int mid = low + (high - low) / 2;
    if (judge(mid)) {
      ans = mid;
      high = mid - 1;
    } else low = mid + 1;
  }
  return ans;
}

其中judge()判断取值为mid的时候是否满足条件，用临时变量ans记录备选结果，随着区间的不断减小，满足条件的备选方案也会不断调整，最后ans表示想要找的结果。

POJ 3273

最小化最大值，也就是求下界问题。

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
37
38
39
40
41
42
43
44
45
46
47
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=1e5+5;
const int Inf=0x3f3f3f3f;
int a[maxn];
int n,m;

bool check(int d)
{
    int sum=0,len=1;
    for(int i=0;i<n;i++){
        if(sum+a[i]<=d){
            sum+=a[i];
        }
        else{
            sum=a[i];
            len++;
        }
    }
    if(len>m) return false;
    else return true;
}
int main()
{
    while(scanf("%d%d",&n,&m)==2)
    {
        int low=0,high=Inf;
        for(int i=0;i<n;i++){
            scanf("%d",&a[i]);
            low=max(low,a[i]);
        }
        int ans;

        while(low<high){
            int mid=low+(high-low)/2;
            if(check(mid)){
                high=mid;
            }
            else{
                low=mid+1;
            }
        }
        printf("%d\n",high);
    }
}
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
37
38
39
40
41
42
43
44
45
46
47
48
49
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=1e5+5;
int a[maxn];
int n,m;

bool check(int d)
{
    int sum=0,len=1;
    for(int i=0;i<n;i++){
        if(sum+a[i]<=d){
            sum+=a[i];
        }
        else{
            sum=a[i];
            len++;
        }
    }
    if(len>m) return false;
    else return true;
}
int main()
{
    while(scanf("%d%d",&n,&m)==2)
    {
        int low=0,high=0;
        for(int i=0;i<n;i++){
            scanf("%d",&a[i]);
            high+=a[i];
            low=max(low,a[i]);
        }
        int ans;

        while(high>=low)
        {
            int mid=(low+high)/2;
            if(check(mid)){
                high=mid-1;
                ans=mid;
            }
            else
                low=mid+1;
        }
        printf("%d\n",ans);
    }
    return 0;
}

求上界

给定长度为$n$的单调不下降子序列$a_0,a_1,…,a_{n-1}$和一个数$k$,求满足$a_i \leq k$条件的最大的$i$

该问题可以转化为求下界问题，满足$a_i>k$条件最小的$i$再减去1即是满足$a_i \leq k$条件的最大的$i$。

也可以写作以下形式：

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
int lower_bound(int k){
    int first=0,last=n;
    //区间为[first,last)
    while(last-first>1){
        int mid=last+(last-first)/2;
        if(a[mid]<=k){
            first=mid;
        }
        else{
            last=mid;
        }
    }
    return first;
}
int lower_bound(int k){
    int first=0,last=n;
    //区间为[first,last)
    while(first<last){
        int mid=last+(last-first)/2;
        if(a[mid]<=k){
            first=mid-1;
        }
        else{
            last=mid+1;
        }
    }
    return first;
}

考虑迭代过程，根据$a[mid]$与$k$的相对大小

  • $a[mid]\leq k$,$mid$点满足$a[mid]\geq k$,所求为满足条件的最大下标，故小于$mid$的部分均可以舍去。左端点可以取到，故取$first=mid$，此解的范围为$[mid,last)$

  • $a[mid]>k$,$mid$不可能为解，右边界不可以取到，所以取$last=mid$,此时解的范围为$[first,last)$

    每次迭代的时候满足$a_i\leq k$的最大下标必然还存在于区间内

循环在满足$first-last \geq1$的时候执行，即在$first==last$的时候停止执行，$(first，last]$此时为空。

给定长度为$n$的单调不下降子序列$a_0,a_1,…,a_{n-1}$和一个数$k$,求满足$a_i < k$条件的最大的$i$

该问题同样可以转化为求下界问题，满足$ a_i \leq k$条件最小的$i$再减去1即是满足$ a_i < k$条件的最大的$i$。

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
int lower_bound(int k){
    int first=0,last=n;
    //区间为[first,last)
    while(first-last>1){
        int mid=last-(last-first)/2;
        if(a[mid]<k){
            first=mid;
        }
        else{
            last=mid;
        }
    }
    return first;
}

int lower_bound(int k){
    int first=0,last=n;
    int ans=-1;
    ////区间为[first,last)
    while(first<=last){
        int mid=first+(last-first)/2;
        if(a[mid]<=k){
            first=mid-1;
            ans=mid;
        }
        else{
            last=mid+1;
        }
    }
    return ans;
}

在求满足条件的最大值往往用以下形式：

1
2
3
4
5
6
7
8
9
10
11
int search(int low, int high) {
  int ans = -1;
  while (low <= high) {
    int mid = low + (high - low) / 2;
    if (judge(mid)) {
      ans = mid;
      low = mid - 1;
    } else high = mid + 1;
  }
  return ans;
}

以上形式便于在找不到符合条件的解时返回-1

POJ 2456

最大化最小值，也就是求上界问题

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
37
38
39
40
41
42
43
44
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
const int maxn=1e5+5;
const int Inf=1e9+5;
int n,c;
int x[maxn];
bool check(int d){
    int last=0;
    for(int i=1;i<c;i++){
        int crt=last+1;
        while(crt<n&&x[crt]-x[last]<d){
            crt++;
        }
        if(crt==n) return false;
        last=crt;
    }
    return true;
}


int main(){
    scanf("%d%d",&n,&c);
    for(int i=0;i<n;i++){
        scanf("%d",&x[i]);
    }
    sort(x,x+n);
    int lb=1,ub=Inf;
    while(ub-lb>1){
        int mid=lb+(ub-lb)/2;
        if(check(mid)){
            lb=mid;
        }
        else{
            ub=mid;
        }
    }
    printf("%d\n",lb);

    return 0;
}
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
37
38
39
40
41
42
43
44
45
46
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
const int maxn=1e5+5;
const int Inf=1e9+5;
int n,c;
int x[maxn];
bool check(int d){
    int last=0;
    for(int i=1;i<c;i++){
        int crt=last+1;
        while(crt<n&&x[crt]-x[last]<d){
            crt++;
        }
        if(crt==n) return false;
        last=crt;
    }
    return true;
}


int main(){
    scanf("%d%d",&n,&c);
    for(int i=0;i<n;i++){
        scanf("%d",&x[i]);
    }
    sort(x,x+n);
    int lb=1,ub=Inf;
    int ans=0;
    while(lb<=ub){
        int mid=lb+(ub-lb)/2;
        if(check(mid)){
            ans=mid;
            lb=mid+1;
        }
        else{
            ub=mid-1;
        }
    }
    printf("%d\n",ans);

    return 0;
}

区间问题

区间中点的选择并不唯一

  1. 上位中位数：uppermid=first+length/2
  2. 下位中位数：lowermid=first+(length-1)/2

在length为偶数时二者取值才不同，分别为中间一对下标中的大者和小者。

区间中点选择上位中位数还是下位中位数差异不大，其余部分不需要跟着调整。

若区间取两端为闭区间时，循环条件应为

1
while(lb<=ub)

若区间一端为开区间，一端为闭区间，循环条件应为

1
while(lb<ub)

若区间两端均为开区间，循环条件应为

1
while(ub-lb<1)

二分思想是利用区间值有序的特点，不断让区间长度减半，最后将区间长度缩小至0或1。

确保二分的正确性，

  1. 每次迭代解均在可行区间内
  2. 每次判断后可行区间都会缩小

在区间为1的时候，左右端点值处理不好就会存在死循环。

浮点数二分

浮点数二分循环条件一般为要求达到的精度或者迭代次数。

1
2
3
4
5
6
7
8
9
10
#define eps 1e-8

double search(double low, double high) {
  while (high - low > eps) {
    double mid = (low + high) / 2;
    if (judge(mid)) high = mid;
    else low = mid;
  }
  return (low + high) / 2;
}

POJ 1064

给$n$条绳子，长度分别为$l_i$,从中切分出$k$条长度相同的绳子，这$k$条绳子最长有多长？

设条件$C(x)=$可以得到$k$条满足长度要求的绳子

问题转变为了求满足$C(x)$条件的最大的$x$

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
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
const int maxn=10005;
const double Inf=100005.0;
double l[maxn];
int n,k;
bool check(double x)
{
    int sum=0;
    for(int i=0;i<n;i++){
        sum+=(int)(l[i]/x);
    }
    if(sum>=k) return true;
    else return false;
}

int main(){
    scanf("%d%d",&n,&k);
    for(int i=0;i<n;i++){
        scanf("%lf",&l[i]);
    }
    double lb=0,ub=Inf;
    for(int i=0;i<100;i++){
        double mid=(lb+ub)/2;
        if(check(mid)) lb=mid;
        else ub=mid;
    }
    printf("%.2f\n",floor(ub*100)/100);

    return 0;
}