std :: lower_bound和std :: upper_bound [保持]的时间复杂度

Question

我在有序向量上使用std::upper_bound，并且显然无法在对数时间内工作，因为我将其与我自己的上限搜索实现进行了比较。为什么会这样呢？我的代码：

for (size_t i = 1; i < sorted_vector.size(); ++i) {
    size_t m = std::upper_bound(
        sorted_vector.begin(),
        sorted_vector.begin() + i,
        values_to_search[i]) - sorted_vector.begin();

这里的总时间应该是O(n * log(n))。当我在大小为50000的数组上使用自己的upper_bound实现时，大约需要花费0.05秒，而使用std则需要大约3秒。

Answer 1

类似，您的sorted_vector的迭代器不是RandomAccessIterator的std::vector，>]。

相反，您可能正在处理forward或bidirectional迭代器，这意味着O（N）用于在二进制搜索中“跨越”容器的距离“跳跃”，而不是O（1）（您已经指出了期待）。

检查以确保sorted_vector是std::vector或类似的字符！