P2249 查找 题解

An_Aholic · 2023-03-27 22:35:32 · 个人记录

P2249 查找

题面理解：

首先看下题，非常易懂，就是给你一个单调不减的序列，给你 m 次询问，每次询问让你找到一个数字q， 如果能找到输出下标，否则就输出“-1”

思路分析：

我这个juruo首先想到的是枚举，但是————（战术性延长）注意：多测！直接枚举时间复杂度就直接** /ll。那怎么办啊？题面给你了很强的提示：单调不减。那很容易想到是二分力！二分，可以这样理解：先把这个序列看做一条线不停的取中点，如果比中点大了（拿单调不减举例），就把左端点合并到中点来取得线段，比中点小同理（把右端点合并到中点来取得线段），然后接着再取这条线段的中点……以此类推，最后一定能找到离我们要找到的那个数的最接近的那个数(很多时候就是我们要找的那个数)的下标。

首先提供个用while循环实现的代码:

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

int n, m, a[1000005];

int find(int l, int r, int x) {

    while (l < r) { 
        int mid = l + (r - l) / 2; // 取中值 
        if (x < a[mid])  // 在左区间 (小于中值), 右端点合并mid 
            r = mid - 1;
        if (x > a[mid])  // 在右区间 (大于中值), 左端点合并mid 
            l = mid + 1;
        if (x == a[mid]) // 在看下在仍 l < r (有别的数)的情况下, 右端点合并mid找左边有没有下标更小的 
            r = mid;
    }
    if (a[r] == x)
        return r;
    else return -1;

}

int main() {
    scanf("%d %d", &n, &m);

    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]);

    for (int i = 1; i <= m; i++) {  // m次询问 
        int win;
        scanf("%d", &win);
        int ans = find(1, n, win); // 调用函数 
        printf("%d ", ans);
    }

    return 0;
}

再提供一个递归法：

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

int n, m, a[1000005];

int find(int l, int r, int x) {
    int mid = l + (r - l) / 2;// 取中值
    if (l < r) {
        if (x > a[mid])
            return find(mid + 1, r, x); // 在左区间 (小于中值), 右端点合并mid
        if (x < a[mid])
            return find(l, mid - 1, x); // 在右区间 (大于中值), 左端点合并mid
        if (x == a[mid])        // 在看下在仍 l < r (有别的数)的情况下, 右端点合并mid找左边有没有下标更小的
            return find(l, mid, x);
    }
    if (a[mid] == x) // 注意这里要用mid, 因为人家r是不会变化滴!
        return mid;
    else return -1;

}

int main() {
    scanf("%d %d", &n, &m);

    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]);

    for (int i = 1; i <= m; i++) {
        int win;
        scanf("%d", &win);
        int ans = find(1, n, win);  // 调用 
        printf("%d ", ans);
    }

    return 0;
}

ok, 完结撒花（不可能） 可是由于二叉的代码又臭又长，一旦写错了一点儿，怎么办？(A:凉拌) C++为了我们不必凉拌 ，给了我们几个锦袋！ 下面我来列举一下：

1. binary_search(beg,end,val) 返回一个bool变量，以二分法检索的方式在[beg,end]之间查找val，找到返回true，找不到返回false。
2. lower_bound(beg,end,val) 返回一个迭代器，指向非递减序列[first, last)中的第一个大于等于（>=）val的位置。
3. upper_bound(beg,end,val) 返回一个迭代器，指向非递减序列[first, last)中的第一个大于 (>) val的位置。