Re: binary search

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

Relevant Pages

  • Re: How optimized is this string searching method?
    ... compared to some better way (e.g. different data structure, ... A faster solution is a binary search with O. ... (hash-table-buckets hash-table) ... and use less than length string characters, ...
    (comp.lang.lisp)
  • Re: How optimized is this string searching method?
    ... compared to some better way (e.g. different data structure, ... A faster solution is a binary search with O. ... Focus on the basic functionality. ... (Overzealous optimizers tend to ...
    (comp.lang.lisp)
  • Re: nearest neighbor in 2D
    ... Ron> function that could speed it up. ... at the outset to set up a data structure which allows a more efficient ... The analogy is a binary search in 1D. ...
    (comp.lang.python)
  • Re: What is the best way to pull out a range of values?
    ... Let's say I have a large collection of values and they are in an array ... It seems to me the data structure you are looking for is a sorted list. ... Then you can use binary search to find the first element above the lower ... "Reply" at the bottom of the article headers. ...
    (comp.lang.perl.misc)
  • Re: tree coloring data problem?
    ... You want a data structure to store the ... > colors of nodes, supporting the following operations: ... > Looking up the color of a node (given a pointer to the node) should be ...
    (comp.programming)