Is It possible to apply binary search to link list to find an element?

Question

I have read a question ,is it possible to apply binary search on a link list?

Since link list doesn't allow random access, this looks practically impossible.

Any one has any way to do it?

Answer 1

for applying binary search on linked list, you can maintain a variable count which should iterate through the linked list and return the total number of nodes. Also you would need to keep a var of type int say INDEX in your node class which should increment upon creation of each new node. after which it will be easy for you to divide the linked list in 2 halves and apply binary search over it.

Answer 2

According to me, there is no way to search the Linked list in binary search manner. In binary search, we usually find out 'mid' value of array which is impossible with lists, since lists are the structure where we have to strictly use the 'start' (Node pointing to very 1st node of list) to traverse to any of our list elements.

And in array, we can go to specific element using INDEX, here no question of Index (Due to Random Access unavailability in linked lists).

So, I think that binary search is not possible with linked list in usual practices.

Answer 3

You can do a binary search on a linked list. As you say, you don't have random access, but you can still find the element with a specific index, starting either from the start of the list or from some other position. So a straightforward binary search is possible, but slow compared with binary search of an array.

If you had a list where comparisons were much, much more expensive than simple list traversal, then a binary search would be cheaper than a linear search for suitably-sized lists. The linear search requires O(n) comparisons and O(n) node traversals, whereas the binary search requires O(log n) comparisons and O(n log n) node traversals. I'm not sure if that O(n log n) bound is tight, the others are.

Answer 4

I have once implemented something like that for a singly-linked list containing sorted keys. I needed to find several keys in it (knowing only one of them at the beginning, the rest were dependent on it) and I wanted to avoid traversing the list again and again. And I didn't know the list length.

So, I ended up doing this... I created 256 pointers to point to the list elements and made them point to the first 256 list elements. As soon as all 256 were used and a 257th was needed, I dropped the odd-numbered pointer values (1,3,5,etc), compacted the even-numbered (0,2,4,etc) into the first 128 pointers and continued assigning the remaining half (128) of pointers to the rest, this time skipping every other list element. This process repeated until the end of the list, at which point those pointers were pointing to elements equally spaced throughout the entire list. I then could do a simple binary search using those 256 (or fewer) pointers to shorten the linear list search to 1/256th (or 1/whatever-th) of the original list length.

This is not very fancy or powerful, but sometimes can be a sufficient perf improvement with minor code changes.

Answer 5

The main issue, besides that you have no constant-time access to the linked list elements, is that you have no information about the length of the list. In this case, you simply have no way to "cut" the list in 2 halves.

If you have at least a bound on the linked list length, the problem is solvable in O(log n), with a skip list approach, indeed. Otherwise nothing would save you from reading the whole list, thus O(n).

So, assuming that the linked list is sorted, and you know its length (or at least the maximum length), yes it's possible to implement some sort of binary search on a linked list. This is not often the case, though.

Answer 6

Not with a classic linked list, for the reasons you state.

But there is a structure that does allow a form of binary search that is derived from linked lists: Skip lists.

(This is not trivial to implement.)

Answer 7

With a plain linked list, you cannot do binary search directly, since random access on linked lists is O(n).

If you need fast search, tree-like data structures (R/B tree, trie, heap, etc.) offer a lot of the advantages of a linked list (relatively cheap random insertion / deletion), while being very efficient at searching.