lower_bound 在 c++ 中表示多个值

Question

假设我有一个从 0 到 1 的排序向量。我想知道索引，其中值变得大于 0.1 的倍数（即 deciles。将来可能还有百分位数）。

我想到的一个简单的解决方案是使用 std::lower_bound:

std::vector<float> v;

/// something which fills the vector here

std::sort(v.begin(),v.end());

std::vector<float>::iterator i = v.begin();
for (float k = 0.1 ; k < 0.99 ; k+= 0.1) {
  i = std::lower_bound (v.begin(), v.end(), k);
  std::cout << "reached " << k << " at position " << (low-v.begin()) << std::endl;
  std::cout << "       going from " << *(low-1) << " to " << *low << std::endl;
  // for simplicity of the example, I don't check if low is the first item of the vector
}

由于向量可以很长，我想知道是否可以让它更快。第一个优化是不搜索前一个十分位数以下的向量部分：

i = std::lower_bound (i, v.end(), k);

但是，假设 lower_bound 执行二进制搜索，这仍然会一遍又一遍地扫描每个十分位数的向量的整个上部，并且不会使用先前二进制搜索的中间结果。

所以理想情况下，我想使用一个搜索功能，我可以将多个搜索项传递给它，有点像：

float searchvalues[9];
for (int k = 1; k <= 9 ; ++k) {
  searchvalues[k] = ((float)k)/10.;
}
int deciles[9] = FANCY_SEARCH(v.begin(),v.end(),searchvalues,9);

标准库、boost 库或其他库中是否已经存在这样的东西？

Answer 1

Boost 或 C++ 标准库中没有任何内容。算法的两个选择，请记住两个向量都已排序：

O(N)：遍历排序后的向量，边走边考虑分位数向量的元素。
O(Log N * Log M)：从中间分位数开始。呼叫lower_bound。其结果在随后的 lower_bound 调用该枢轴下方的分位数集合中成为较高迭代器，并在随后的 lower_bound 调用该枢轴上方的分位数集合中成为较低的迭代器。对两半重复该过程。

对于百分位数，我的感觉是 (1) 将是更快的选择，并且实施起来要简单得多。

Answer 2

要进入 O(log n)，您可以使用以下内容：

void fill_range(
    std::array<boost::optional<std::pair<std::size_t, std::size_t>>, 10u>& ranges,
    const std::vector<float>& v,
    std::size_t b,
    std::size_t e)
{
    if (b == e) {
        return;
    }
    int decile_b = v[b] / 0.1f;
    int decile_e = v[e - 1] / 0.1f;

    if (decile_b == decile_e) {
        auto& range = ranges[decile_b];

        if (range) {
            range->first = std::min(range->first, b);
            range->second = std::max(range->second, e);
        } else {
            range = std::make_pair(b, e);
        }
    } else {
        std::size_t mid = (b + e + 1) / 2;
        fill_range(ranges, v, b, mid);
        fill_range(ranges, v, mid, e);
    }
}

std::array<boost::optional<std::pair<std::size_t, std::size_t>>, 10u>
decile_ranges(const std::vector<float>& v)
{
    // assume sorted `v` with value x: 0 <= x < 1
    std::array<boost::optional<std::pair<std::size_t, std::size_t>>, 10u> res;
    fill_range(res, v, 0, v.size());
    return res;
}

Live Demo

但线性搜索似乎更简单

auto last = v.begin();
for (int i = 0; i != 10; ++i) {
    const auto it = std::find_if(v.begin(), v.end(),
                                 [i](float f) {return f >= (i + 1) * 0.1f;});
    // ith decile ranges from `last` to `it`;

    last = it;
}

lower_bound 在 c++ 中表示多个值

lower_bound for more than one value in c++

c++

search

vector

binary-search