21

在阅读http://en.cppreference.com/w/cpp/algorithm/binary_search时，我注意到它将转发迭代器作为参数。现在我很困惑，因为我认为它宁愿是一个随机访问迭代器，所以二进制搜索实际上是二进制的。

为了满足我的好奇心，我写了一个小程序：

#include <iostream>
#include <vector>
#include <forward_list>
#include <list>
#include <deque>
#include <algorithm>
#include <chrono>
#include <random>

int main()
{
    std::uniform_int_distribution<int> uintdistr(-4000000, 4000000);
    std::mt19937 twister(std::chrono::high_resolution_clock::to_time_t(std::chrono::high_resolution_clock::now()));
    size_t arr[] = { 200000, 400000, 800000, 1600000, 3200000, 6400000, 12800000 };
    for(auto size : arr)
    {
        std::list<int> my_list;
        for(size_t i = 0; i < size; i++)
            my_list.push_front(uintdistr(twister));
        std::chrono::time_point<std::chrono::high_resolution_clock> start, end;
        my_list.sort(); //fixed
        start = std::chrono::high_resolution_clock::now();

        std::binary_search(my_list.begin(), my_list.end(), 1252525);

        end = std::chrono::high_resolution_clock::now();
        long long unsigned elapsed_time = std::chrono::duration_cast<std::chrono::microseconds>(end-start).count();
        std::cout << "Test finished in " << elapsed_time << "\n";
    }
}

使用 gcc 4.7.0 编译并运行

g++ -std=c++11 test.cpp

在我的机器上提供以下结果：

Test finished in 0
Test finished in 15625
Test finished in 15625
Test finished in 46875
Test finished in 93750
Test finished in 171875
Test finished in 312500

所以看起来它实际上并没有在前向列表上进行二进制搜索。现在我的问题是：

为什么会有这样一个令人困惑的名字？

为什么允许这样的代码？

为什么参考文献说它是“第一个和最后一个之间距离的对数”？

标准对此有何规定？

编辑：现在代码在搜索之前对列表进行排序 - 愚蠢的错误，现在结果是：

Test finished in 46875
Test finished in 109375
Test finished in 265625
Test finished in 546875
Test finished in 1156250
Test finished in 2625000
Test finished in 6375000

当然仍然不是对数的；）

4

3 回答 3

19

源自该标准的原始 SGI STL 实现的文档指出

比较次数是对数的：最多 log(last - first) + 2。如果ForwardIterator是随机访问迭代器，则通过范围的步数也是对数；否则，步数与 last - first 成正比。

也就是说，比较的次数总是对数的，而由于缺乏随机可访问性而影响的进步次数可以是线性的。在实践中，stl::advance可能使用 ，如果迭代器是随机访问，则复杂度是恒定的，否则是线性的。

如果比较非常昂贵，则具有线性数量的迭代器改进但具有对数比较数的二进制搜索是有意义的。例如，如果您有一个复杂对象的排序链表，需要磁盘或网络访问才能进行比较，那么使用二分搜索可能比使用线性搜索要好得多。

于 2012-11-21T21:14:34.203 回答
6

与网站可能说的相反（例如“对数distance(first, last)”），该标准实际上只谈到了比较（例如 25.4.3.1, lower_bound）：

复杂性：最多log2(last − first) + O(1)比较

迭代器的递增不包括在复杂度中！请注意，尽管标准库要求所有迭代器增量都具有摊销常数复杂性，因此增加迭代器会产生 O(N) 的订单成本（但大概这有一个非常小的主要因素）。特别是（25.4.3）：

对于非随机访问迭代器 [算法] 执行线性数量的步骤。

于 2012-11-21T21:18:37.100 回答
2

该标准指定排序搜索算法（std::lower_bound()、std::upper_bound()和std::binary_search()）以线性时间为正向和二进制迭代器工作。对于随机访问，时间是对数的。

但是请注意，数量comparisons限制为对数。

于 2012-11-21T21:18:08.173 回答