algorithm - 帮我写一个边界值的二进制搜索(提取子列表)

Question

假设我有一个包含很多值的数组(C++ 语法，抱歉):

vector<double> x(100000);

此数组排序为 x[n] > x[n-1]。

我想要一个函数来检索范围 [a, b](含)内所有值的数组。一些界面如:

void subarray(const double a, const double b, vector<double> &sub) {
    ...
}

当此函数完成时，sub 将包含落在 [a, b] 范围内的 n 值。

当然线性搜索很简单:

void subarray(const double a, const double b, vector<double> &sub) {
    for (size_t i = 0; i < data.size(); i++) {
        if (a <= data[i] && data[i] <= b) {
            sub.push_back(data[i]);
        }
    }
}

但是，因为 data 是排序的，我应该能够使用二进制搜索更快地完成这项工作。谁想试一试？允许使用任何语言!

Answer 1

您要问的是关于确切范围属性和类型的问题。但是，您可以调整以下 C++ 代码以满足您的需要。基本的直觉是使用 lower_bound 和 upper_bound 在数组中找到描绘您要查找的范围的位置。

void subarray(const double a, const double b, vector <double> &sub, vector <int> pn) {
    vector <int>::const_iterator begin, end;
    begin = lower_bound(pn.begin(), pn.end(), a);
    end = upper_bound(pn.begin(), pn.end(), b);
    sub.insert(sub.begin(), begin, end);
}