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

algorithm data-structures linked-list binary-search asymptotic-complexity
unk1102 picture unk1102 · Mar 12, 2011 · Viewed 50.3k times · Source

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

Steve Jessop picture Steve Jessop · Mar 12, 2011

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.

Related questions

How is it possible to do binary search on a singly-linked list in O(n) time?

This earlier question talks about doing binary search over a doubly-linked list in O(n) time. The algorithm in that answer work as follows: Go to the middle of the list to do the first comparison. If it's equal to …

Read More
How to reverse a singly linked list using only two pointers?

I wonder if there exists some logic to reverse a singly-linked list using only two pointers. The following is used to reverse the single linked list using three pointers namely p, q, r: struct node { int data; struct node *link; }; …

Read More
How to detect a loop in a linked list?

Say you have a linked list structure in Java. It's made up of Nodes: class Node { Node next; // some user data } and each Node points to the next node, except for the last Node, which has null for next. Say …

Read More