QLU_ACM 浅谈二分搜索技术

by StilllFantasy

二分思想为何物？

二分查找也称折半查找（Binary Search），它是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。

关键点：

• 优点：每次折半，速度较快
• 缺点：待查表必须为顺序表-->二分搜索的限制
• 复杂度：O ( log N )

什么意思？

简而言之就是，待查表必须是有序的，无序的话必须先排序，比如在数组二分搜索某个数的时候

举个栗子：

    int a[10] = {1,2,3,4,5,6,7,8,9};

• 朴素查找

int search(int K)
{
    for (int i = 0; i < N; i++)
        if (num[i] == K)
        {
            return i;
        }
    return -1;
}

• 二分查找

int search(int K, int L, int R)
{
    int l = L;
    int r = R;
    while (l <= r)
    {
        if(l == r && num[l] != K)
            return -1;

        int mid = (l + r) / 2;

        if (num[mid] < K)
            return search(K, mid + 1, R);

        else if (num[mid] > K)
            return search(K, L, mid - 1);

        else
            return mid;
    }
    return -1;
}

二分不难写吧？

• 其实二分的思想还是蛮容易理解的
• 重点在于：它除了能在数组里查数用，还能干啥呢？

二分答案！

• 特点：速度快、神奇

注意：

• 答案满足单调性
• 预估答案区间 minAns ~ maxAns

步骤：

找区间-->取中间判断是不是答案-->折半直到找到答案

关于此类题目的一般关键词：

• 最大值尽量小
• 最小值尽量大
• (在某种情况下)最小值是多少
• (在某种情况下)最大值是多少

说到这里，新手可能有点蒙，没关系，我们来看几个例题：

It is the time to 举栗子！

例题Z：买糖

小朋有个弟弟，小凯。小凯喜欢哭鼻子，经常因为没糖吃而哭鼻子。小朋要哄着小凯，给小凯买糖吃，小朋有 N 元钱，商店老板小康卖的糖 K 元一个，共有 M 个，小凯多吃一块糖就少哭一次，但事实也不是任由小凯的，他吃糖就会把糖纸乱扔，弄得校园很脏，校园里脏的程度y与小凯吃糖个数x关系是：y=x^2-20181314*x,当校园里脏的程度超过 S 时，小凯的姐姐小林就会打她，小凯虽想吃糖但他不想挨打啊，问小凯在不被挨打的情况下，最多可以少哭多少次？
数据范围 1<=K,N,M,S<=10^9

• （这题不要当真，瞎搞用的，测试一波O(N)与O(logN)的差距）

#include <iostream>
#include <cmath>
using namespace std;
long long n,m,k,s;
int ok=1;
bool isok(int z)
{
    if(z<=m&&z*k<=n&&2*z<=s)
    {
        return 1;
    }
    else return 0;
}
int main()
{
    cin>>n>>m>>k>>s;

    ///朴素查找
    for(int i=1;i<=m;i++)
    if(!isok(i))
    {
        cout<<"ans is "<<i<<endl;
        ok=0;
        break;
    }
    if(ok)
    cout<<"ans is "<<m<<endl;
   
    ///二分查找
    long long l=1,r=m;
    long long ans;
    while(l<=r)
    {
        long long mid=(l+r)/2;
        if(isok(mid))
        {
            l=mid+1;
            ans=mid;
        }
        else r=mid-1;
    }
    cout<<"ans is "<<ans;  
    return 0;
}

例题A：安排牛棚 ->链接

#include <iostream>
#include <algorithm>
#include <cstdio>
using namespace std;
int x[100005];
int c, n;
int R, L = 1e9 + 9;
int s;
int ans;
bool ansok(int key)
{
    int now = 1; //now表示上一个放牛的牛棚编号，因为第一次在一号牛棚放下，所以now=1
    int sum = 1; //sum表示放的牛的个数，初始时我们肯定把第一个牛棚放上牛，所以sum=1
    for (int i = 2; i <= n; i++)
    {
        if (x[i] - x[now] >= key)
        {
            sum++;
            now = i;
        }
    }
    if (sum >= c)
        return 1;
    else
        return 0;
}
int main()
{
    cin >> n >> c;
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &x[i]);
        s = max(s, x[i]);
        L = min(L, x[i]);
    }
    sort(x + 1, x + 1 + n);
    R = s / c + 1;
    while (L <= R)
    {
        int mid = (L + R) / 2;
        if (ansok(mid))
        {
            L = mid + 1;
            ans = mid;
        }
        else
            R = mid - 1;
    }
    cout << ans;
    return 0;
}

/*
    ansok(int key) ：
    我们假设key就是最小值，那么我们就尝试按照这样的最小值能不能把牛给安排下
    如果两个牛棚之间的距离小于key，那么这个牛棚不能放牛，因为我们已经假设了key是最小值
    这个选择的过程不理解的话模拟一下就可以
*/

例题B：跳石头 ->链接

#include <iostream>
#include <algorithm>
using namespace std;
int N, M, L;
int minAns = 1e9 + 9;
int maxAns;
int ans;
int dis[50006];
bool ansok(int key)
{
    int sum = 0;
    int now = 0;
    for (int i = 1; i <= N + 1; i++)
    {
        if (dis[i] - dis[now] < key)
            sum++;
        else
            now = i;
    }
    if (sum <= M)
        return 1;
    else
        return 0;
}
int main()
{
    cin >> L >> N >> M;
    for (int i = 1; i <= N; i++)
    {
        cin >> dis[i];
    }
    dis[N + 1] = L;     //虚拟一个终点 N+1
    int left = 0;
    int right = L;
    while (left <= right)
    {
        int mid = (left + right) / 2;
        if (ansok(mid))
        {
            ans = mid;
            left = mid + 1;
        }
        else
        {
            right = mid - 1;
        }
    }
    cout << ans;
    return 0;
}
/*
    这题有一个坑在于起点到终点的距离要大于第 N 个点到起点的距离
    我们虚拟一个 N+1 点，来判断第 N 个石头是不是要拿走 
*/

例题C：组装玩具 ->链接

• 这题可以用二分解决，但不像是之前两个题那么“模板化” ，需要注意的地方要单独处理，本题深入沟通可以私聊我QQ

#include <iostream>
#include <algorithm>
using namespace std;
struct toy
{
    int a;
    int b;
    int c;
} s[1000006];
int n, m;
int cnt;
int ans = 0;
int sum;
int k[1000006];
bool cmp(toy x, toy y)
{
    return x.c < y.c;
}
int ifok(int k)     //判断二分出的答案是否可行
{
    int mm = 0;
    for (int i = 0; i < n; i++)
    {
        if (s[i].c >= k)
            return m - mm;
        mm += k * s[i].b - s[i].a;
        if (m - mm < 0)
            return m - mm;
    }
    return m - mm;
}
int main()
{
    cin >> n >> m;
    for (int i = 0; i < n; i++)
        cin >> s[i].a;

    for (int i = 0; i < n; i++)
    {
        cin >> s[i].b;
        s[i].c = s[i].a / s[i].b;
        sum += s[i].b;
    }
    sort(s, s + n, cmp);
    for (int i = 0; i < n; i++)
    {
        if (k[cnt] != s[i].c)
            k[++cnt] = s[i].c;
    }
    int mm = ifok(k[cnt] + 1);
    if (mm == 0)
        cout << cnt + 1;
    else if (mm > 0)
        cout << mm / sum + k[cnt] + 1;
    else    //本题核心：二分答案
    {
        int l = 0;
        int r = k[cnt];
        while (l <= r)
        {
            int mid = (l + r) / 2;
            if (ifok(mid) >= 0)
            {
                ans = mid;
                l = mid + 1;
            }
            else
            {
                r = mid - 1;
            }
        }
        cout << ans;  
    }
    return 0;
}

 cout << "Hello, QLU_ACM_club !!!" << endl;