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

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.

Leave a Comment