; binary search
(define (range . args)
(case (length args)
((1) (range 0 (car args) (if (negative? (car args)) -1 1)))
((2) (range (car args) (cadr args) (if (< (car args) (cadr args)) 1 -1)))
((3) (let ((le? (if (negative? (caddr args)) >= <=)))
(let loop ((x(car args)) (xs '()))
(if (le? (cadr args) x)
(reverse xs)
(loop (+ x (caddr args)) (cons x xs))))))
(else (error 'range "unrecognized arguments"))))
(define-syntax assert
(syntax-rules ()
((assert expr result)
(if (not (equal? expr result))
(for-each display `(
#\newline "failed assertion:" #\newline
expr #\newline "expected: " ,result
#\newline "returned: " ,expr #\newline))))))
(define (bsearch lt? x xs)
(let loop ((lo 0) (hi (- (vector-length xs) 1)))
(let ((mid (quotient (+ lo hi) 2)))
;(display lo) (display " ") (display mid)
;(display " ") (display hi) (newline)
(cond ((< hi lo) #f)
((lt? x (vector-ref xs mid))
(loop lo (- mid 1)))
((lt? (vector-ref xs mid) x)
(loop (+ mid 1) hi))
(else mid)))))
(define (test-bsearch n)
(do ((i 0 (+ i 1))) ((= n i))
(let ((xs (list->vector (range 0 n 2))))
(do ((j -1 (+ j 1))) ((< n j))
(if (and (even? j) (< j n))
(assert (bsearch < j xs) (/ j 2))
(assert (bsearch < j xs) #f))))))
(test-bsearch 25)