洛谷题单指南-二分查找与二分答案-P2249 【深基13.例1】查找

原题链接：https://www.luogu.com.cn/problem/P2249

题意解读：找有序数组中某个数第一次出现的位置，二分模版题，由于是二分板块的第一题，有必要对二分的各种模版进行介绍。

解题思路：

关于二分的一切：

1、二分的本质

二分的本质，是通过某种判定把目标范围划分成两个区间

二分问题通常有两种要求：

a、找绿色范围的起始值 b、找红色范围的结束值

初始给定目标范围的最小、最大值：l、r

取中间值mid = (l + r) / 2

根据某种逻辑check(mid)进行判定mid属于哪个区间

对于要求a：如果属于绿色区间，更新答案，继续在l ~ mid - 1之间寻找；否则在mid + 1 ~ r之间寻找。

对于要求b：如果属于红色区间，更新答案，继续在mid+1 ~ r之间寻找；否则在l ~ mid - 1之间寻找。

因此，二分就有两种模版。

2、整数二分：

模版1：找绿色范围的起始值

int bs1(int l, int r)
{
    int res = -1;
    while(l <= r)
    {
        int mid = (l + r) >> 1; 
        if(check(mid)) 
        {
            res = mid;
            r = mid - 1;
        }
        else l = mid + 1;
    }
    return res;
}

说明：

a、(l + r) >> 1等同于(l + r) / 2，区别在于如果l + r是负数，除以2会向上取整，而整数是向下取整，>> 1的方式就是统一向下取整。

b、check(mid)表示判定mid是符合绿色范围的

模版2：找红色范围的结束值

int bs2(int l, int r)
{
    int res = -1;
    while(l <= r)
    {
        int mid = (l + r) >> 1; 
        if(check(mid)) 
        {
            res = mid;
            l = mid + 1;
        }
        else r = mid - 1;
    }
    return res;
}

说明：check(mid)表示判定mid是符合红色范围的

3、实数二分：

模版1：

int bs1(double l, double r)
{
    while(r - l > 1e-8)
    {
        double mid = (l + r) / 1; 
        if(check(mid)) r = mid;
        else l = mid;
    }
    return r;
}

由于实数没有连续性，在更新区间边界的时候，直接用r = mid或l = mid；

另外，实数无法精确判断相等，采用r - l > 1e-8，如果差大于一个很小的数，认为基本相等且r不会在l左边

通常，这个很小的数可以根据题目要求的保存的小数位置确定，例如题目要求保留2位小数，则可以取1e-4，比要求多2位即可。

模版2：

int bs2(double l, double r)
{
    while(r - l > 1e-8)
    {
        double mid = (l + r) / 1; 
        if(check(mid)) l = mid;
        else r = mid;
    }
    return r;
}

其实，对于实数二分，模版1和模版2没有区别，可以在check的时候通过返回值来统一成一套模版。

回到本题：

要找数字第一次出现的位置，显然是找绿色范围的起始值，对应模版1，只不过题目要求如果要找的数不存在则返回-1，在结果返回之前判断一下即可：

100分代码：

#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 5;

int a[N], q, n, m;

int bs(int x)
{
    int l = 1, r = n, res = -1;
    while(l <= r)
    {
        int mid = (l + r) >> 1;
        if(a[mid] >= x) 
        {
            res = mid;
            r = mid - 1;
        }
        else l = mid + 1;
    }
    if(a[res] == x) return res;
    return -1;
}

int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i++) cin >> a[i];
    for(int i = 1; i <= m; i++) cin >> q, cout << bs(q) << " ";

    return 0;
}