search

[Chris Torek]

In article <184 at stsim.UUCP> glenn at stsim.UUCP (Glenn Ford) writes:
>... search's on a sorted database. ... Is there a faster, yet fairly easy
>to implement, routine that can search my database?  Faster than binary
>search..  I don't want B-Tree's.  My database is allready built.

An interpolative search will run in O(log log n) time rather than
O(log n) in the `average' case.  Coding these is not too terribly
tricky (one assumes that if a[0] is 0 and a[10] is 100, then a[1] is
10, a[2] is 20, etc., until it is otherwise demonstrated).  But what
you really want to do is minimise read operations (since you are
reading off slow media), which suggests that the algorithm be tweaked
slightly: read big blocks (if they are contiguous media-wise) and look
at the edges of the block before switching blocks.

You will do better, though, if you rebuild the database.
-- 
In-Real-Life: Chris Torek, Univ of MD Comp Sci Dept (+1 301 454 7163)
Domain:	chris at mimsy.umd.edu	Path:	uunet!mimsy!chris