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将包含n范围 [a, b] 内的值。

当然，线性搜索很容易：

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);
}

Answer 2

您似乎已经知道可以使用二进制搜索来查找范围，并且很容易找到它们的实现。

其他一切都只是简单的数组操作。

Answer 3

简单的解决方案：

• 使用二分查找找到最低的 a 和最高的 b
• 分配一个新数组
• 复制值

如前所述，代码是微不足道的。