Subj : Re: binary search
To   : comp.programming
From : Richard Heathfield
Date : Thu Jul 28 2005 07:20 am

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

.