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

In Forth?

--
Goyim were born only to serve us. Without that, they have no place in the
world---only to serve the People of Israel.... They will work, they will plow,
they will reap. We will sit like an effendi and eat. --- Rabbi Ovadia Yosef
web.archive.org/web/20101020044210/http://www.jpost.com/JewishWorld/JewishNews/Article.aspx?id=191782
archive.org/download/DavidDuke_videos/TopRabbiExposesJewishRacism-cybsdwjezqi.ogv