; 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)