Subj : Re: binary search
To   : comp.programming
From : Ed Prochak
Date : Fri Jul 29 2005 05:51 am


Scott Moore wrote:
> 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.

rather than sorting that arry, this pass could just do the linear
search. If you are going to visit each list item, then checking the
value isn't much bigger in cost.
>
> 3. Quicksort the array.

The list is already sorted. this is just a waste of time.

>
> 4. Form a new list from the array.
>
> 5. Dispose of the array.

Did you actually read the initial problem description??????

.