CODEWITHSUNDEEP
data-structureslinked-listbinary-search
Kishan Raval
Kishan Raval

Reputation: 89

Binary Search in Linked List

Is there any use of Binary Search Algorithm in Sorted Linked List? Or is it useful any how in any way? I know that in array it is very efficient to use Binary Search as we know the address of all elements. But in linked List, we have to traverse through every Node.

Upvotes: 2

Views: 982

Answers (2)

sundar
sundar

Reputation: 414

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

Upvotes: 1

Good Luck
Good Luck

Reputation: 1102

The reason to use binary search is to find a number in o(log n). It is however impossible for a linked list. The use of a tree or an array is suggested. Take a look at this:

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

Upvotes: 1

Related Questions