binary search

[Robert L.]

Tayssir John Gabbour wrote:

> Incidentally, instead of -1, you'll want to return NIL upon failure.
>
> Here's a version using LOOP:
>
> (defun binary-search (vector item)
> (loop with low = 0
> with high = (1- (length vector))
> for middle = (truncate (+ low high) 2)
> for middle-obj = (aref vector middle)
> do (format t "~&{~S, ~S}, ~S" low high middle) ;debugging
> while (<= low high)
> if (< middle-obj item) do (setf low (1+ middle))
> else if (> middle-obj item) do (setf high (1- middle))
> else do (return middle)
> finally (return nil)))


(require srfi/43) ; vector operations

(define vec #(0 2 4 5 8 9 20 22 23 26 27 30))

(vector-binary-search vec 22 (compose sgn -))
===>
7

(vector-binary-search vec 88 (compose sgn -))
===>
#f


--
Jews totally run Hollywood.... But I don't care if Americans think we're
running the news media, Hollywood, Wall Street, or the government. I just care
that we get to keep running them. --- Joel Stein
articles.latimes.com/2008/dec/19/opinion/oe-stein19
archive.org/download/DavidDukeTv/DoJewsControlTheMediaTheLaTimesSaysYes.flv