二分查找是否具有 deque C++ 的对数性能？数据结构？
标准规定 std::binary_search(...) 以及两个相关函数 std::lower_bound(...) 和 std::upper_bound( ...) 如果数据结构具有随机访问，则为 O(log n)。因此，鉴于此，我假设这些算法在 std::deque 上具有 O(log n) 性能（假设其内容由用户排序）。
然而，似乎 std::deque 的内部表示很棘手（它被分成了块），所以我想知道： O(log n) 搜索的要求是否适用于 std ::双端队列。
The standard says that std::binary_search(...) and the two related functions std::lower_bound(...) and std::upper_bound(...) are O(log n) if the data structure has random access. So, given that, I presume that these algorithms have O(log n) performance on std::deque (assuming its contents are kept sorted by the user).
However, it seems that the internal representation of std::deque is tricky (it's broken into chunks), so I was wondering: does the requirement of O(log n) search hold for std::deque.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
是的，它仍然适用于
deque，因为容器需要在常数时间内提供对任何元素的访问（只是比vector稍高的常数）。但这并不能免除您对双端队列进行排序的义务。
Yes it still holds for
dequebecause the container is required to provide access to any element in constant time (just a slightly higher constant thanvector).That doesn't relieve you of the obligation for the
dequeto be sorted though.是的。双端队列对索引（如果存在）具有恒定时间访问权限。它被组织成大小相等的页面。你所拥有的是某物。就像指向页面的指针向量。如果您有 2 个包含 100 个元素的页面，并且您想要访问第 103 个元素，则通过 103/100 = 1 确定页面并通过 103 %100 => 确定页面中的索引3. 现在在两个向量中使用恒定时间访问来获取元素。
这是来自 http://www.cplusplus.com/reference/stl/deque/：
Yes. deque has constant time access for an index if it is there. It is organized in pages of an equal size. What you have is smth. like a vector of pointers to pages. If you have let's say 2 pages with 100 elements and you would like to access 103rd element than determine the page by 103/100 = 1 and determine the index in the page by 103 %100 => 3. Now use a constant time access in two vectors to get the element.
Here the statement from http://www.cplusplus.com/reference/stl/deque/:
写一个程序来测试一下，我认为deque的binary_search实现会比vector慢，但它的复杂度仍然是O(logn)
Just write a program to test that, I think deque's implementation of binary_search will slower than vector's, but it's complexity is still O(logn)