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

Ged_Relay · 2020-02-29 18:07:22 · 题解

本蒟蒻第一次发题解QWQ求过

**首先题目意思是给一串已经排好了的数字问你某个数字的位置。\ 如果从1到n扫一遍的话肯定超时。\ 所以这里用了二分的方法：

**首先找到这串数字中间位置的那个数，然后与需要查询的数比较

如果要查询的数小于中间那个数，那么答案肯定在左边

如果要查询的数大于中间那个数，那么答案肯定在右边

如果等于的话继续在左边找，因为找到的位置还不能确定是第一个数

如此重复，直到要查询的区域变为1。

以下是AC代码：

#include<cstdio>
#include<algorithm>
#include<iostream>
using namespace std;
int a[1000020];
int findpos(int a[], int l, int r, int k)
{
    if (l == r)
    {
        if (a[l] == k)
            return l;
        else
            return -1;/*最后位置的数与待查询数不相等，说明数列里没有此数*/
    }
    int mid = (l + r) / 2;
    if (k <= a[mid])
        findpos(a, l, mid, k);/*在左边区域找*/
    else
        findpos(a, mid + 1, r, k);/*在右边区域找*/
}
int main()
{
    int n, m, k;
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    while (m--)
    {
        cin >> k;
        cout << findpos(a, 1, n, k) << " ";
    }
    return 0;
}