I'm a newbie at LISP and I'm exploring LISP. Right now, I'm trying to
convert a pascal program I wrote a long time ago that performs a binary search
on a sorted list. Purpose of my original program (in Pascal) was to compare the
performance with other search algorithms. That was easy, in Pascal I mean. In
LISP? Well, I figured it's got to be some kinda function (BinSearch key list)
which returns T or F depending of whether key is in list or not. Guess I've
been pampered by iterative programming for too long. LISP sure is different.
Any help would be much appreciated. Thanks.
Joe Yong.
Joe Yong (······@iastate.edu) wrote:
: on a sorted list. Purpose of my original program (in Pascal) was to compare the
: performance with other search algorithms. That was easy, in Pascal I mean. In
: LISP? Well, I figured it's got to be some kinda function (BinSearch key list)
: which returns T or F depending of whether key is in list or not. Guess I've
: been pampered by iterative programming for too long. LISP sure is different.
If you're considering lists, there's no efficient way. In a binary
search you need direct access to the middle of the sequence of sorted
data, but a list is basically a linear structure.
However you can perform similiar search on binary trees or vectors.
Then you may use intutive pattern like this (I dunno LISP syntax
for accessing vectors, sorry) :
(defun search (l r key data)
(let ((m (/(+ l r) 2))))
(cond ((= l r) .. not found)
((= data[m] key) ..found..)
((> data[m] key) (search l m key data))
((< data[m] key) (search m r key data))
)))
--
plato. rene descartes.william somerset maugham. albert einstein.alan turing
pablo picasso.homer.nicolaus copernicus PALADIN MU georg
cantor. lau tzu . kurt goedel .johnann ········@cc.nctu.edu.tw seb
astian bach. alonzo church.claude monet DEP. OF CIS, NCTU. TAIWAN donald
knuth.charles babbage.john backus.von neumann.william shakespeare.aristotle