c++ - 查找排序范围内元素数量的最快方法是什么？

Question

给定一个排序列表
1, 3, 5, 6, 9....
是否有一种快速算法，而不是O(n)计算给定范围内的元素数量[a, b]，假设所有数字都是整数？

Answer 1

这是一个 O(log n) 算法：使用二分搜索搜索两个端点，范围内的元素数量基本上就是索引的差异。

要获得确切的数字，需要区分范围端点是否在数组中的情况。

Answer 2

由于列表已排序，因此您可以在 O(log(n)) 时间内找到值的位置（或者，如果该值不在列表中，则应将其插入到哪里）。您只需对两端执行此操作并减去即可获得范围内元素的数量。元素是否为整数没有区别；列表只需要排序。

如果元素不是唯一的，您确实需要小心；在这种情况下，在找到命中后，您可能需要对重复元素序列的末尾进行线性扫描。

Answer 3

lower_bound并对upper_bound已分类的容器进行操作。

首先找到该范围内的较低值，然后从那里搜索到最后的较高值。函数的实现可能使用二进制搜索：

#include <algorithm>
#include <list>
#include <iterator>

int main() {
    using std::list;
    using std::upper_bound;
    using std::lower_bound;
    using std::distance;

    list<int> numbers = {1, 3, 5, 6, 9};
    int a = 3;
    int b = 6;

    auto lower = lower_bound(numbers.begin(), numbers.end(),
                             a);
    auto upper = upper_bound(lower, numbers.end(),
                             b);

    int count = distance(lower, upper);

    return 0;
}