Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!sun-barr!lll-winken!elroy.jpl.nasa.gov!usc!ucsd!ucbvax!ucdavis!iris!lim
From: lim@iris.ucdavis.edu (Lloyd Lim)
Newsgroups: comp.theory
Subject: Re: lower-bound for searching sorted sequences (was: binary search)
Message-ID: <8274@ucdavis.ucdavis.edu>
Date: 31 Jan 91 00:21:49 GMT
References: <56531@eerie.acsu.Buffalo.EDU> <56707@eerie.acsu.Buffalo.EDU>
Sender: usenet@ucdavis.ucdavis.edu
Reply-To: lim@iris.ucdavis.edu (Lloyd Lim)
Organization: U.C. Davis - Department of Electrical Engineering and Computer Science
Lines: 31

In article <56707@eerie.acsu.Buffalo.EDU> sarnath@acsu.buffalo.edu (Ramnath Sarnath) writes:
>In article <56531@eerie.acsu.Buffalo.EDU> I wrote:
>
>This needs a clarification... what I wanted to prove was that searching
>a sorted sequence (by any means) is not possible in time faster than
>O(logn).

You can search faster than O(log n).  Interpolation search comes to mind.
Basically, you guess or interpolate the next postion to look at based on
the value to just saw.

From Udi Manber's "Introduction to Algorithms" (since I can't say it any
better myself):

"The performance of interpolation search depends not only on the size of the
sequence, but also on the input itself.  There are inputs for which
interpolation search checks every number in the sequence.  However,
interpolation search is very efficient for inputs consisting of relatively
uniformly distributed elements.  It can be shown that the average number of
comparisons preformed by interpolation search, where the average is taken over
all possible sequences, is O(log log n).  Although this seems to be an order of
magnitude improvement over the performace of binary search, interpolation
search is not much better than binary search in practice for two main reasons.
First, unless n is very large, the value of log n is small enough that the
logarithm of it is not much smaller.  Second, interpolation search requires
more elaborate arithmetic."

+++
Lloyd Lim     Internet: lim@iris.eecs.ucdavis.edu
              Compuserve: 72647,660
              US Mail: 215 Lysle Leach Hall, U.C. Davis, Davis, CA 95616