how to apply binary search O(log n) on a sorted linked list?

Question

Recently I came across one interesting question on linked list. Sorted singly linked list is given and we have to search one element from this list.

Time complexity should not be more than O(log n). This seems that we need to apply binary search on this linked list. How? As linked list does not provide random access if we try to apply binary search algorithm it will reach O(n) as we need to find length of the list and go to the middle.

Any ideas?

Answer 1

It is certainly not possible with a plain singly-linked list.

Sketch proof: to examine the last node of a singly-linked list, we must perform n-1 operations of following a "next" pointer [proof by induction on the fact that there is only one reference to the k+1th node, and it is in the kth node, and it takes a operation to follow it]. For certain inputs, it is necessary to examine the last node (specifically, if the searched-for element is equal to or greater than its value). Hence for certain inputs, time required is proportional to n.

You either need more time, or a different data structure.

Note that you can do it in O(log n) comparisons with a binary search. It'll just take more time than that, so this fact is only of interest if comparisons are very much more expensive than list traversal.

Answer 2

You need to use skip list. This is not possible with a normal linked list (and I really want to learn if this is possible with normal list).