Subj : Re: binary search
To   : comp.programming
From : Scott Moore
Date : Thu Jul 28 2005 03:20 pm

Marc Dansereau wrote:
> JD wrote:
> 
> 
>>Given a sorted linked list it is required to perform a binary search
>>for a particular element. Kindly suggest an optimum algorithm for the
>>problem.
> 
> 
> Binary search is not a practical solution for linked list. Mabe you can
> search google for skip list wich is probably a better solution.

1. Allocate an array of pointers with the same number of units
as the list.

2. Place a pointer to each element of the list in the array.

3. Quicksort the array.

4. Form a new list from the array.

5. Dispose of the array.

.