P2249 【深基13.例1】查找 的题解

· · 个人记录

先看看题目# 【深基13.例1】查找

题目描述

输入 n 个不超过 10^9 的单调不减的（就是后面的数字不小于前面的数字）非负整数 a_1,a_2,\dots,a_{n}，然后进行 m 次询问。对于每次询问，给出一个整数 q，要求输出这个数字在序列中第一次出现的编号，如果没有找到的话输出 -1 。

样例 #1

样例输入 #1

11 3
1 3 3 3 5 7 9 11 13 15 15
1 3 6

样例输出 #1

1 2 -1

也就是说我们要找这里q的第一次出现的位置。那么最先想到的方法不就是循环搜索吗？代码如下：

#include<bits/stdc++.h>
using namespace std;
#define Max 1000006
int a[Max], n, m;
int main() {
    ios::sync_with_stdio(false);
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    int op = 0;
    for (int i = 1; i <= m; i++) {
        cin >> op;
        for (int j = 1; j <= n; j++)
            if (a[j] == op)
                cout << j << " ";
    }

    return 0;
}

但是很明显，这题的n和m分别是1 \leq n \leq 10^6，0 \leq a_i,q \leq 10^9，1 \leq m \leq 10^5 按照双重循环的做法应该是O(nm)具体一点是10^6+10^11 这绝对会超时

果然不出所料绝对超时

那我们应该就是用二分了 （题目都叫二分了）

首先搞懂什么是二分，二分就是每次放弃一半

那我们应该舍弃哪一半呢，根据正常人思维，因该是没有答案的那一半舍弃吧，什么你说舍弃答案那一部分？ 你**的**去**

那我们就能推出如下代码：

int fond(int ans) {
    int l = 1, r = n, mid,k=0;
    while (l < r) {
        mid = (l + r) / 2;
        if (a[mid] >= ans) r = mid;
        else l = mid + 1;
    }
    if(a[l]==ans)
        k=l;
    else
        k=-1;
    return k;
}

其中ans 代表的是答案，mid是中间分割的位置，l和r是目前选的下标的范围

那这些代码怎么解读呢

先定义l 和 r是两边的界（如同两哨兵，我们只用他们之间的数）

mid用于标出两边的界限

如果我们要求的在左边我们就让r去到mid，反之则让l去到mid+1

思考，为什么l要加一

答：不然永远死循环，但是如果r也减一的话，如果mid就是答案的话就会直接跳过，所以r到mid就好。

那为什么用的是l而不是r做答案呢，因为l才是我们要找到，因为条件是l在左，r在右（有些写法是用r做答案的，这里建议都用l做）

然后如果我们找不到，那么我们就返回-1，那这题的完整代码就是

#include<bits/stdc++.h>
using namespace std;
#define Max 1000006
int a[Max], n, m;
int fond(int ans) {
    int l = 1, r = n, mid,k=0;
    while (l < r) {
        mid = (l + r) / 2;
        if (a[mid] >= ans) r = mid;
        else l = mid + 1;
    }
    if(a[l]==ans)
        k=l;
    else
        k=-1;
    return k;
}
int main() {
    ios::sync_with_stdio(false);
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    int op = 0;
    for (int i = 1; i <= m; i++) {
        cin >> op;
        cout << fond(op) << " ";
    }

    return 0;
}

先输入n,m

然后逐个输入a

再输入op 也就是题目的q

然后二分找q

二分具体方法和解释见上

扩展：

1.#include<bits/stdc++.h> 是万能头文件，基本包含了所有函数

2.ios::sync_with_stdio(false); 分类输出和缓存空间，提升输出输入的速度具体见这