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.
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.