P2249. 查找

发表于 分类于 阅读次数： Waline： 本文字数： 191 阅读时长 ≈ 1 分钟

考点

  • 二分

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <bits/stdc++.h>

using namespace std;

const int LEN = 1e6 + 50;

int arr[LEN];

int binary_search(int x, int n)
{
    int l = 1, r = n;
    while (l <= r)
    {
        int mid = l + (r - l) / 2;
        if (arr[mid] >= x)
            r = mid - 1;
        else
            l = mid + 1;
    }
    if (arr[l] == x)
        return l;
    return -1;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, m, in;
    cin >> n >> m;
    for (int i = 1; i <= n; ++i)
        cin >> arr[i];
    while (m--)
    {
        cin >> in;
        cout << binary_search(in, n) << " ";
    }
    return 0;
}

思路

直接找左边界即可

当然也可以选择使用lower_bound函数，在离散化的时候也经常用到

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <bits/stdc++.h>

using namespace std;

const int LEN = 1e6 + 10;

int arr[LEN];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, m, in, idx;
    cin >> n >> m;
    for (int i = 1; i <= n; ++i)
        cin >> arr[i];
    while (m--)
    {
        cin >> in;
        cout << (arr[idx = lower_bound(arr + 1, arr + 1 + n, in) - arr] == in ? idx : -1) << " ";
    }
    return 0;
}