Re: binary search

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.

.

Relevant Pages

  • Re: What is the best way to pull out a range of values?
    ... Then you can use binary search to find the first element above the lower ... That's exactly what binary search does, in log n time for lists of ... I don't know for sure if the "data" array is static or it is being ... int chkndx = pos; ...
    (comp.lang.perl.misc)
  • Re: Buggy BinarySearch implementation, real life and a curious soul...
    ... typical daily array size? ... So either roll your own binary search function, ... So my question's audience are people who had both CL and Java ... the Modula-2 language specifies that overflow errors are detected: ...
    (comp.lang.lisp)
  • Re: binary search
    ... >> Binary search is not a practical solution for linked list. ... Allocate an array of pointers with the same number of units ... Place a pointer to each element of the list in the array. ...
    (comp.programming)
  • Re: searching an array, string compare functions, string sorting
    ... array is not generated with JavaScript. ... When searching a word in the index, I do a quick binary search. ... exactly the way as JavaScript would sort them. ... Javascript sort can be given a user-written compare function, ...
    (comp.lang.javascript)
  • Re: Reading & Searching a Huge file
    ... then I think you could take advantage of the fact that the lines are all _almost_ the same length and do a binary search on the file itself. ... This is, I think, what you're suggesting when you wrote "read all the numeric values sequentially into some array"; you didn't mention also storing the file offsets for each record, but hopefully you realize that's implied since otherwise keeping the values in an array wouldn't be useful. ... keep in mind that this is the sort of thing that databases are really good at. ...
    (microsoft.public.dotnet.languages.csharp)