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

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.

Binary search is, of course, a much easier alternative.

The problems come when your linked list is not stored in an array, but in a 
bunch of arbitrary memory locations hooked together with pointers. In such 
a situation, the trick is to have the proper pointers - i.e. the ones you 
need.

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


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

.