• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

P2249 有序序列中查找元素题解

开发技术 开发技术 6小时前 2次浏览

题目传送门

标准的二分查找模板是两个,一个用于查找指定元素的左边界,另一个用于查找指定元素的右边界。举个栗子:

([0,1,3,3,3,4,5,6])

如果二分查找(3)的第一个位置,就是(pos=2),如果二分查找(3)的最后一个位置,就是(pos=4)

P2249的答案

#include <bits/stdc++.h>

using namespace std;
int n, m, k;
const int N = 1e6 + 10;
int a[N];

//要求输出这个数字在序列中第一次出现的编号
//就是左侧第一个,如果发现
bool check(int x) {
    return a[x] >= k; //如果大于等于k,就是可以x再小一点,就是向左
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> a[i];
    //进行 m 次询问
    while (m--) {
        cin >> k;
        int l = 1, r = n; //从第1个到第n个,这个范围很清楚。
        while (l < r) {
            int mid = (l + r) >> 1;
            if (check(mid))r = mid; //向左!
            else l = mid + 1;       //不行再向右!
        }
        //如果找完,发现这个位置不是我们要找的值,说明没有结果存在于数组中
        if (a[l] != k)printf("%d ", -1);
        else printf("%d ", l);
    }
    return 0;
}

程序员灯塔
转载请注明原文链接:P2249 有序序列中查找元素题解
喜欢 (0)