C++ STL Deque 搜索：太慢？

Question

我目前正在学习竞争性编程课程。我遇到了一个函数调用问题，其中一个任务要求我在双端队列中找到一个值。不幸的是，我当前的实现具有时间复杂度 O(N)，而且速度太慢。

我的代码是这样的：

deque<int>::iterator find(int ref) {
    for (deque<int>::iterator it = d.begin(); it != d.end(); ++it) {
        if (*it == ref) return it;
    }
    return d.begin();
}

四处询问后，我发现我需要对数时间复杂度 O(log N) 以避免超出时间限制 (TLE) 错误。请帮忙，谢谢！

Answer 1

如果内容已排序，您可以使用二进制搜索：http://en.cppreference.com/w/cpp/algorithm/binary_search
在地图上更改双端队列：http://www.cplusplus.com/reference/map/map/find/（大小为对数。）

C++ STL Deque 搜索：太慢？

C++ STL Deque search: too slow?

c++

stl

deque

function-call