C++（相关搜索：二分查找）

Question

二分查找与二分答案
确定数字个数
题目难度：高阶
时间限制：5000ms
内存限制：128MB
C++题目描述
输入n(n<=10的6次方)个不超过10的9次方的单调不减的（就是后面的数字不小于前面的数字）非负整数 a1,a2,...an，然后进行m(m<=10的5次方)次询问。对于每次询问，给出一个整数q（q<=10的9次方），要求输出这个数字在序列中出现的次数。

输入格式
第一行 2 个整数 n 和 m，表示数字个数和询问次数。

第二行 n 个整数，表示这些待查询的数字。

第三行 m 个整数，表示询问这些数字的编号，从 1 开始编号。

输出格式
m 个整数表示答案。

输入输出样例
输入 #1

11 3
1 3 3 3 5 7 9 11 13 15 15
1 3 6
输出 #1

1 3 0

Answer 1

这道题并不难，是一个典型的二分查找统计问题，由于输入的数组是单调不减的，所以可以通过二分查找快速确定某个数字在数组中的出现次数。
代码很简单，使用c++标准库很容易实现。

#include <iostream>
#include <vector>
#include <algorithm>

int main(int argc, char *argv[])
{
    int n, m;
    std::cin >> n >> m;

    std::vector<int> numbers(n);
    for (int i = 0; i < n; ++i)
    {
        std::cin >> numbers[i];
    }

    std::vector<int> queries(m);
    for (int i = 0; i < m; ++i)
    {
        std::cin >> queries[i];
    }

    for (int i = 0; i < m; ++i)
    {
        int q = queries[i];
        auto lower = std::lower_bound(numbers.begin(), numbers.end(), q);
        auto upper = std::upper_bound(numbers.begin(), numbers.end(), q);

        int count = upper - lower;
        std::cout << count << "\n";
    }

    system("pause");
    return 0;
}

运行后，根据需要输入数据，并返回；