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?

Rondi

The cop-out answer is that if you're needing to perform a binary search, then you're using the wrong data structure. :) – Foust

Isn't this why skiplists were invented? – Ayeshaayin

If anyone is still interested in this, here is a DS I came up with that does exactly this: cs.stackexchange.com/questions/137076/… – Vandusen

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.

Ulmaceous

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

Division

Skip list is the solution for binary search with linked list. Its not possible with normal linked list. – Wondawonder

This should be the accepted answer. The top-voted answer is either misleading or incomplete. It only says that "you probably need something else" which is not very amazing. This answer hits the spot. – Burden

You can't use a skiplist. The question regards a singly-linked list. – Blear

This answers clearly answers the "singly-linked list" case. The SkipList is provided as a reasonable alternative. – Burden

Answer 3

In Linked List, binary search may not achieve a complexity of O(log n) but least can be achieved a little by using Double Pointer Method as described here in this research work: http://www.ijcsit.com/docs/Volume%205/vol5issue02/ijcsit20140502215.pdf

Rayerayfield

The method given by the paper in your link is even worse than a linear search since to find middle pointer will waste a lot of time. – Acarid

Answer 4

As noted, this is not in general possible. However, in a language like C, if the list nodes are contiguously allocated, it would be possible to treat the structure as an array of nodes.

Obviously, this is only an answer to a trick question variant of this problem, but the problem is always an impossibility or a trick question.

Blear

What would be the point of a linked list if the nodes are contiguously allocated? – Klenk

@MarkRansom To give the interview question setter a feeling of superiority? To test for candidates who can work quickly with weird, crufty code? I do note that this is a trick answer to a trick question, after all. – Blear

It's not even a trick answer, as if you rely on elements being stored contiguously you give up the main advantage of it being a linked list - O(1) insertion/deletion time. So it's better than to use an ordinary array, and not bother about the linked list. – Burden

@Burden Actually, no - that's exactly what you don't lose. The advantage of such a structure is that in contiguously allocated areas, you can go back easily, BUT you can also insert (resulting in a non-contiguous list). – Blear

Well, so after you've made that insert and don't have contiguous list any more than what's the point of it being contiguous at first? – Burden

@Burden Well (a) insertions may be rare; (b) that's not the point. This is a trick answer to a trick question. – Blear

@Blear Even if they're rare, one of them spoils the whole structure. So there is no point in it. This is not a "trick question" - it has a practical meaning, and that's why a structure called SkipList exists. And that's why SkipList is the only valid answer to this question. Therefore I find this answer (as well as the top-voted answer) misleading. – Burden

@Burden No, a skiplist is not a valid answer because the question specifically specifies a singly linked list. I'm sorry that you're so narrowly focused on what you think the question should be, that you can't address the actual question asked. – Blear

The answer with a skip list is the best answer because: 1) It answers the question directly saying that this is impossible with single linked list. 2) It provides a sensible alternative, as close to the presented problem as possible. I've downvoted every answer I've deemed deserving a downvote, don't worry. As a side note, I'm wondering who downvoted the skiplist answer recently - that doesn't seem wise, rather envious. – Burden

@Burden This answer notes that it is impossible in the general case. You just like skiplists. As to "It provides a sensible alternative, as close to the presented problem as possible" that is nice, but it's not a reason to downvote answers which don't answer the question you wish had been asked. – Blear

Answer 5

Yes, it is possible in java language as below..

Collections.<T>binarySearch(List<T> list, T key)

for binary search on any List. It works on ArrayList and on LinkedList and on any other List.

Moncton

List have very different meaning in context of Collection, refer official doc – Tabular

Answer 6

Use MAPS to create LINK LISTS.
Map M , M[first element]=second element , M[second element]=third element ,
...
...
its a linked list...
but because its a map...
which internally uses binary search to search any element..
any searching of elements will take O(log n)

Elfland

Obviously trick questions and answers ...nobody cares of here ..what is wrong in this answer..can you explain Marcin – Elfland

You either need more time, or a DIFFERENT DATA STRUCTURE(Steve Jessop) – Elfland

I downvoted this because it is incomprehensible, and as far as I can make sense of it, it does not address the question. – Blear

incomprehensible..how..it definately answer the question..linked list built with log n search time...and again ...DIFFERENT DATA STRUCTURE(Steve Jessop)...similar to this you can find in how link list is built in associative arrays in perl – Elfland

(a) Profligate use of ellipsis and vertical space (b) you don't describe the datastructure fully, but it sounds like it's the required singly-linked list. – Blear

Does not answer the question because the question states that the sorted linked list has been provided from outside the algorithm -- you do not control it. While it is potentially legitimate to introduce a new data structure, the cost of constructing that data structure must be included in the cost of the solution. That is, you are given the sorted linked list. Your solution would create a map based on that linked list and search that map. Time complexity to create the map is at best O(n lg n), and that for the search is O(lg n). So the solution is O(n lg n + lg n), which is O(n lg n). – Karli