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

· · 题解

STL天下第一

这一题的意思就是在一个有序的序列中查找某个数，并要求输出其下标。按照常规思路，如果我们每次枚举当前下标的数并与输入的数对比，时间复杂度是O(n)的，这个复杂度在数据量较小的时候或许还可以接受，但是当数据量特别大的时候呢？我们可能运气好第一数就枚举到了正确的答案，但是如果题目数据强坑我们可能就要枚举到最后一位答案了。

那么我们可不可以考虑每次都从中间找呢？答案是可行的！因为序列是有序的，所以如果我们找到了一个大于目标数据的值，就可以认为这个区间的数都比目标大，即可舍去这个区间。这就是二分查找。

说了这么多反正你们也都会

用到的函数

__lower_bound(start, end, target):从在start到end区间内查找target，如果找到了，返回一个指针，如果没找到，返回第一个比它大的值的指针。__

#include <iostream>
// 边长数组，这样我们就不用担心数据装不下了
#include <vector>
using namespace std;
vector<int > vec;
int main() {
    int n, m;
    int t;
    cin >> n >> m;
    int index;
    // 向数组尾部放入数据，因为这个特性，vector也可以当成stack用
    while(n--) cin >> t, vec.push_back(t);
    while(m--) {
        cin >> t;
        // 在序列里查找目标数据
        index = lower_bound(vec.begin(), vec.end(), t) - vec.begin();
        // 如果目标数据找到了，输出答案，注意我们的数组下标是从0开始的
        if (t == vec[index]) cout << index + 1 << ' ';
        // 没找到记得输出-1哦
        else cout << -1 << ' ';
    }
    return 0;
}

感谢你看完本蒟蒻的题解QWQ