Binary Search on a Doubly Linked List

Question

It is possible to perform binary search on a doubly-linked list in Θ(log 𝑛) time?

My answer is yes because if the list is already somewhat ordered it could be faster than just O(n).

Answer 1

As you asked the question, the answer is no. You cannot have O(lg(n)) time for a linked list since traversal is linear, it cannot be better than O(n) in general, but binary search would be worse than a linear scan in that case since it must iterate multiple times to "jump" around. It would be better to do a single linear scan to find the element.

However, the C++ standard specifies that std::lower_bound algorithm (which does a binary search) has the following complexity:

[lower.bound]

Complexity: At most log2(last - first) + O(1) comparisons and projections.

That is, it is counting the element comparisons, not time, if you are measuring time by number of iterator advancements. That is, it finds the proper place by calling std::advance() on an iterator many times, but each of those calls on a list will be O(N) iterator advancements but on random access containers it's a constant, and for each call to advance there would be a corresponding call to the comparator.

That's why it is always so important to be clear what big-oh notation is measuring. Often the comparisons are a proxy for time, but not always!

Answer 2

In order to do a binary search on a doubly-linked list, you're going to have to first iterate to the halfway-point of the list, so that you can do your first recursion on the two halves of the list.

Iterating to the halfway-point of a linked list is already an O(n) operation, since the time it takes to iterate to the halfway-point will grow linearly as the list itself gets longer.

So you're already at O(n) time, even before you've done any actual searching. Hence, the answer is no.