Re: binary search

Alf P. Steinbach wrote:

> * Richard Heathfield:
>> 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.
>>
>> It depends. If your sorted linked list is stored in an array and you have
>> numerical data approximating to a function that is easily differentiated,
>> then you might want to look into calculus-based methods such as
>> Newton-Raphson, as these converge much more quickly (when they converge
>> at all!) than binary search.
>
> If it is a linked list then binary search doesn't usually apply, no matter
> whether the nodes are in an array or not.
>
> The only applicable case would be where a moron has decided to link each
> array element to the next one.

Yes. But a non-moron wouldn't be trying to do binary search on a linked
list, would he?

>> This technique breaks the transitivity of N->next->prev == N (that is,
>> this relationship, which typically holds for a double-linked list, albeit
>> not at the extreme ends, is NOT true for the list-like data structure I
>> have described),
>
> This is not in general a list data structure, it's a simple (unbalanced)
> binary tree; in particular, it's _not_ a linked list as the OP required.

But it *is* a linked list. It is a list, and it has links. It's just not
quite as flat as lists usually are. :-)

>> but the pay-off is that you can do a binary search trivially,
>> starting at the first item and using simple comparison to find the item
>> quickly, chasing "prev" and "next" pointers at each level.
>
> If the data comes in sorted your procedure will build a degenerate tree,
> which is indeed list-like, and in that case searching is O(n).

That's certainly true. Solutions range from "not using it if the input data
is sorted" right the way up to "AVL".


--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999
http://www.cpax.org.uk
mail: rjh at above domain
.

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: Creating a differences procedure
    ... Since you speak of performing binary search, may I presume you are using ... A pair of lists of indices, ... As you search, mark those ... what you call the "brute force method" will outperform the "pointless binary search method". ...
    (comp.programming)
  • 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 ... "Reply" at the bottom of the article headers. ...
    (comp.lang.perl.misc)
  • Re: Creating a differences procedure
    ... Since you speak of performing binary search, may I presume you are using ... A pair of lists of indices, ... As you search, mark those ... positions of A are missing from B, and all the unmarked positions of B ...
    (comp.programming)
  • Re: C program - Decision Question - IF then ?
    ... i think that the best way to do this for large lists is to ... > sort both of them and then walk through the lists ... to keep sorted you would need to do a binary search for insertion ... String compares are relatively expensive so ...
    (comp.programming)