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

* 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.


> Let each node have two pointers, which you can call "prev" and "next". Since 
> most people call them "left" and "right", the tricksy naming might fool 
> your tutor into thinking you have a simple double-linked list (but it might 
> not). When building your list, store the first item "as is". When the 
> second item comes in, compare it to the first. If it's less, store it, and 
> point the first item's "prev" pointer at it. Otherwise, store it and point 
> the first item's "next" pointer at it. Recurse.
>
> 
> 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.

That's why the pointers in this structure are called 'left' and 'right'.

The names you suggest are highly misleading.


> 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).

-- 
A: Because it messes up the order in which people normally read text.
Q: Why is it such a bad thing?
A: Top-posting.
Q: What is the most annoying thing on usenet and in e-mail?

.