Friday, May 25, 2007

Can we do a Binary search on a linked list?

Great C datastructure question!

The answer is ofcourse, you can write a C program to do this. But, the question is, do you really think it will be as efficient as a C program which does a binary search on an array?

Think hard, real hard.

Do you know what exactly makes the binary search on an array so fast and efficient? Its the ability to access any element in the array in constant time. This is what makes it so fast. You can get to the middle of the array just by saying array[middle]!. Now, can you do the same with a linked list? The answer is No. You will have to write your own, possibly inefficient algorithm to get the value of the middle node of a linked list. In a linked list, you loosse the ability to get the value of any node in a constant time.

One solution to the inefficiency of getting the middle of the linked list during a binary search is to have the first node contain one additional pointer that points to the node in the middle. Decide at the first node if you need to check the first or the second half of the linked list. Continue doing that with each half-list.

4 comments:

Anonymous said...

Skip List is a variant of Linked list that can be used to perform binary search on linked list

Anonymous said...

I loved as much as you'll receive carried out right here. The sketch is tasteful, your authored subject matter stylish. nonetheless, you command get bought an impatience over that you wish be delivering the following. unwell unquestionably come more formerly again since exactly the same nearly very often inside case you shield this hike.

Also visit my web blog ... graduate certificate

Anonymous said...

I think this is one of the mоst important info fоr me.
Anԁ i'm glad reading your article. But should remark on few general things, The site style is ideal, the articles is really great : D. Good job, cheers

Also visit my website ... profitbusinessathome.net

Anonymous said...

It's appropriate time to make some plans for the future and it is time to be happy. I've read thіs
pοst anԁ if I cоuld Ι desire tο suggest you some intereѕting things
or tiрs. Perhаps уou can write next artіcles referring tο
thiѕ articlе. I ωant to rеad morе things
about it!

Fеel freе to visit my ωеblоg http://wiki.base72.com/index.php/Index.php