Does binary search have logarithmic performance of

Question

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.

Answer 1

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/:

Deques may be implemented by specific libraries in different ways, but in all cases they allow for the individual elements to be accessed through random access iterators, with storage always handled automatically (expanding and contracting as needed).

Answer 2

Yes it still holds for deque because the container is required to provide access to any element in constant time (just a slightly higher constant than vector).

That doesn't relieve you of the obligation for the deque to be sorted though.

Answer 3

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)