Re: binary search

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
.

Relevant Pages

  • Re: Slow string search/fast binary search
    ... | I assumed a single repne scasd instruction would be faster than ... | setting up a binary search for blocks smaller than 30 pointers or so. ... | or does it "like" my binsearch loop particularly well - ...
    (comp.lang.asm.x86)
  • Slow string search/fast binary search
    ... I assumed a single repne scasd instruction would be faster than ... setting up a binary search for blocks smaller than 30 pointers or so. ... Is this processor particluarly bad with std - rep scasd - ...
    (comp.lang.asm.x86)
  • Re: single link list , binary search
    ... have the traversal overhead added to that. ... which is equivalent to the sorted array you mentioned. ... You can't do a binary search on a linked list. ... of pointers, you can do a binary search on the array of pointers. ...
    (comp.lang.c)
  • 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: 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)