算法总结——二分法

发表于 | 分类于 | 阅读次数:
字数统计: 1,871 字

汇集二分法常见的题目

二分法

二分法是一个非常常用的算法技巧，用于在多条排序记录中快速找到待查找的记录。相比遍历需要O(n)将时间复杂度优化到了O(logn)，但是需要一组序列本身是有序的。

写二分代码的关键在于处理好其边界情况

下面是一个标准的二分代码：

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 search(int array[], int n, int v)
{
    int left, right, middle;
    // 赋初值，判断是左闭右闭还是左闭右开
    left = 0, right = n - 1;
    // 退出条件，有小于和小于等于两种写法
    while (left <= right)
    {
        // 中值计算，有向下取整和向上取整
        middle = (left + right) / 2;
        if (array[middle] > v)
        {
            // 边界值更新，判断是否需要加一
            right = middle;
        }
        else if (array[middle] < v)
        {
            // 边界值更新，判断是否需要加一
            left = middle;
        }
        else
        {
            return middle;
        }
    }

    return -1;
}

正如上面的注释中所示，写好一个二分算法只需要注意这4个地方：

  1. 赋初值，判断是左闭右闭还是左闭右开
  2. 退出条件，有小于和小于等于两种写法，小于等于对应的是上面“右闭”的情况，因为最后一个可能是要查找的值
  3. 中值计算，有向下取整和向上取整两种方案
  4. 边界值更新，加一或者不变，根据实际情况进行判断（一般是判断是否需要舍弃这一个值）

左右边界的开闭

左闭右闭还是左闭右开应该对应不同的写法，主要的区别在于最后一个值的舍弃问题

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
50
51
52
53
54
// 左闭右闭 [0, n-1] 写法
int search2(int array[], int n, int v)
{
    int left, right, middle;

    left = 0, right = n - 1;

    while (left <= right)
    {
        middle = (left + right) / 2;
        if (array[middle] > v)
        {
            right = middle - 1;
        }
        else if (array[middle] < v)
        {
            left = middle + 1;
        }
        else
        {
            return middle;
        }
    }

    return -1;
}

// 左闭右开 [0, n) 写法
int search3(int array[], int n, int v)
{
    int left, right, middle;

    left = 0, right = n;

    while (left < right)
    {
        middle = (left + right) / 2;

        if (array[middle] > v)
        {
            right = middle;
        }
        else if (array[middle] < v)
        {
            left = middle + 1;
        }
        else
        {
            return middle;
        }
    }

    return -1;
}

死循环

一般如果向下取整和左边界更新不加一组合就可能造成死循环，同理向上取整和右边界不减一组合也可能造成死循环

溢出问题

在一些比较特殊的情况下middle = (left + right) / 2这种写法可能造成溢出问题，更加保险的写法是middle = left + (right - left) / 2;

比较完善的写法

《编程珠玑》中提供了一个给出了比较完成的二分法代码写法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int search4(int array[], int n, int v)
{
    int left, right, middle;
    left = -1, right = n;
    while (left + 1 != right)
    {
        middle = left + （right － left) / 2;
        if (array[middle] < v)
        {
            left = middle;
        }
        else
        {
            right = middle;
        }
    }

    if (right >= n || array[right] != v)
        right = -1;

    return right;
}

2018春招腾讯笔试题

试题地址

题意

小Q的父母要出差N天，走之前给小Q留下了M块巧克力。小Q决定每天吃的巧克力数量不少于前一天吃的一半，但是他又不想在父母回来之前的某一天没有巧克力吃，请问他第一天最多能吃多少块巧克力

题解

可以构造出理想的情况应该是：前面是一个数开始，然后不断除2（向上取整），直到变为1，最后一直持续1。这样把这个序列分为两段：前面类似等比序列，后面都是1

这样我们知道序列的第一个数就知道了以这个数开头的序列总和最少是多少（按照上面的规则计算），这样我们可以从m-n+1开始一直往1当做第一个数遍历，找到第一个满足最小总和少于m的数。便能够得到答案。

这种情况和二分法的常见题型是不是很像，找到第一个满足某种情况的数，而且这个序列还是一个单调序列。用一个二分法加速

代码

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
#include <iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
using namespace std;

int sum(int n, int p)
{
    int sum = 0;
    while(p--)
    {
        sum += n;
        n = (n+1)/2;
    }
    return sum;
}

void solve()
{
    int n, m;
    cin>>n>>m;
    int l = 1, r = m-n+1;
    while(l<r)
    {
        int tem = (l+r+1)/2;
        if(sum(tem, n) <= m)
            l = tem;
        else
            r = tem - 1;
    }
    cout<<l<<endl;
}

int main()
{
    solve();
    return 0;
}

POJ 3258

River Hopscotch

题意

给出一条河对岸中n个石子的坐标（加上起点和终点），现在移走m个石子，要求两个石子间的最小值最大，这个最大的最小值

题解

这个一道经典的二分题目，最大化最小值问题。在查找过程中判断一个数是否满足条件的时候，我们可以转化成判断满足这个最小值需要移走的石子数，通过跟给定的石子数进行比较来判断这个数是否满足条件，最后通过二分找到这个最大的值。

代码

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
using namespace std;
#define INF 0x3f3f3f3f
typedef long long ll;
const int maxn=50005;
int l,n,m;
int d[maxn];
bool judge(int s)
{
	int j=0,num=0;
	for(int i=1;i<n;i++)
	{
		if(d[i]-d[j]<s) num++;
		else j=i;
	}
	//cout<<"s:"<<s<<"num:"<<num<<"m:"<<m<<endl;
	return num<=m;
}
int fun()
{
	int ll=0,rr=l+1;
	int mid;
	while(ll+1<rr)
	{
		mid=(ll+rr)>>1;
		//cout<<ll<<" "<<rr<<" "<<mid<<endl;
		if(judge(mid))
			ll=mid;
		else
			rr=mid;
	}
	return ll;
}
void solve()
{
	while(scanf("%d %d %d",&l,&n,&m)!=EOF)
	{
		for(int i=1;i<=n;i++)
			scanf("%d",&d[i]);
        d[0]=0;
		d[n+1]=l;
		n+=2;
		sort(d,d+n);
		int ans=fun();
		printf("%d\n",ans);
	}
}

POJ 3273

Monthly Expense

题意

给出包含n个元素的数组，将这n个元素分成最多m段，问各种分法中每段和的最大值得最小值是多少

题解

最小化最大值问题，使用二分进行求解，需要注意的是，在不断二分的时候边界更新的时候，当中间值不满足条件的时候，新的区间应该是[mid+1,r]，满足条件的时候新的区间应该是[l,mic].即要排除掉不满足条件的数

代码

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
using namespace std;
#define INF 0x3f3f3f3f
typedef long long ll;
const int maxn=100010;
int n,m;
int d[maxn];

bool judge(int s)
{
    int num=0,tmp=0;
    for(int i=0;i<n;i++)
    {
        if(tmp+d[i]<=s) tmp+=d[i];
        else
        {
            tmp=d[i];
            num++;
        }   
    }
    if(tmp) num++;
    return num<=m;
}

int fun(int maxv,int sum)
{
    int l=maxv,r=sum,mid;
    while(l<r)
    {
        mid=(l+r)/2;
        if(judge(mid)) r=mid;
        else l=mid+1;
    }
    return l;
}

void solve()
{
    while(scanf(“%d %d”,&n,&m)!=EOF)
    {
        int sum=0,maxv=0;
        for(int i=0;i<n;i++)
        {
            scanf(“%d”,&d[i]);
            sum+=d[i];
            maxv=max(maxv,d[i]);
        }
        printf(“%d\n”,fun(maxv,sum));
    }
}