GDUT ACM2022寒假集训 专题一 G（二分查找）

GDUT ACM2022寒假集训 专题一 G（二分查找）

更好的阅读体验请前往：Paxton的小破站

一、二分查找 1、原理

如果要在一个有序数列中查找一个数的位置，首先想到的应该是遍历一遍数组逐个寻找。但是这样做会有一个问题，当查找请求变得非常多的时候，时间复杂度就变成了O(n*m)，很容易爆时间。

因此我们可以使用二分查找的方法来解决问题。

二分查找的基本思路就是，每次都取当前区间的中间值，如果等于目标，则返回结果。否则，判断目标值与中间值的大小关系，调整左右边界，选择丢弃掉一半的元素，再继续执行二分查找，如下图所示。

开始时左右边界标记都不位于数列中，逐次取中间值，缩小左边界或右边界直到左右边界标记相遇即结束循环，但在实际问题中往往中间值取到目标位置即得出结果。在上图中我们进行了五行 *** 作，但实际第四行即得结果。

这样子进行查找的时间复杂度是 O(logN) ，空间复杂度是 O(1) ，相比起直接遍历查找效率有很大的提升。

2、伪代码

l=0,r=N+1 //数列范围1-N
while l+1 ≠ r
    mid = (l+r)/2
    if IsLeft(m)
        l=mid
    else
        r=mid
return l or r

3、注意

（1）数列必须是有序数列
（2）根据题目实际情况合理更改 Isleft(m) 判断条件和return返回值
（3）l，r边界标记起始时不在数列内

二、例题

原题链接：https://vjudge.net/contest/477276#problem/G

1、题干

给定一个严格单调的数列，询问若干个数分别需要在数列中二分几次才能找到。如果能找到，输出二分的次数；如果不能找到，输出 NONE。

2、输入格式

第一行两个整数 n,m 分别表示数列长度和询问次数。

第二行 n 个整数，第 i 个表示 ai

接下来 m 行，每行一个整数 x 表示要求询问的数。

3、输出格式

共 m 行，如果能找到，输出二分的次数，如果不能找到，输出 NONE。

4、数据范围

对于 40% 的数据：1≤n≤106 ,1≤m≤106 ,1≤x,ai≤106

对于100% 的数据：1≤n≤106 ,1≤m≤ 5 x 106 ,1≤x,ai≤106

5、提示

读入/出数据量较大，请使用 scanf/printf。

6、样例

Sample Input

10 4
1 2 3 5 7 9 11 12 13 14
7
6
5
4

Sample Output

1
NONE
4
NONE

三、题解 1、分析

根据题目给的数据范围，可能存在查询的次数比数列长度大得多的情况，也就是进行重复查询，显然按照一般思路输入一个数字查询一次肯定会超时。

因此我们可以提前将数列中的每一个数字需要的二分查找的次数都算出来并用一个新的数组进行存储，查询时直接输出对应的数字即可。

2、代码

#include 
using namespace std;
int n, m, l, r, num, mid;
int a[1000001];
int b[1000001];

int main()
{
    freopen("A.in", "r", stdin);
    freopen("A.out", "w", stdout);
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; ++i)
    {
        scanf("%d", &a[i]);//读入数列
    }
    bool pd = 0;//pd用于判断数列递增递减
    if (a[1] > a[2])
    {
        pd = 1;
    }

    for (int i = 1; i <= n; ++i)//遍历数列
    {
        l = 0, r = n + 1, num = 0;
        while (l + 1 != r)//对数列中每一个数进行二分查找
        {
            mid = (l + r)/2;
            num++;
            if (a[mid] == a[i])//中值为结果直接结束二分
            {
                break;
            }
            if (pd == 0)//递增
            {
                if (a[mid] < a[i])
                {
                    l = mid;
                }
                else
                {
                    r = mid;
                }
            }
            else//递减
            {
                if (a[mid] > a[i])
                {
                    l = mid;
                }
                else
                {
                    r = mid;
                }
            }
        }
        if(a[mid]==a[i])//进行存储
        {
            b[a[i]] = num;
        }
    }


    int x;
    while(m--)//逐个读入查询数并输出结果
    {
        scanf("%d", &x);
        if(b[x])
        {
            printf("%dn", b[x]);
        }
        else
        {
            printf("NONEn");
        }
    }
}