; ternary search
(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 (+ lo (quotient (- hi lo) 2))))
(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 (tsearch lt? x xs)
(let loop ((lo 0) (hi (- (vector-length xs) 1)))
(let ((lomid (+ lo (quotient (- hi lo) 3)))
(himid (- hi (quotient (- hi lo) 3))))
(cond ((< hi lo) #f)
((lt? x (vector-ref xs lomid)) (loop lo (- lomid 1)))
((lt? (vector-ref xs himid) x) (loop (+ himid 1) hi))
((not (lt? (vector-ref xs lomid) x)) lomid)
((not (lt? x (vector-ref xs himid))) himid)
(else (loop (+ lomid 1) (- himid 1)))))))
(define xs '#(2 3 5 7 11 13 17 19 23 29 31 37 41 43 47))
(display (bsearch < 7 xs)) (newline)
(display (bsearch < 14 xs)) (newline)
(newline)
(display (tsearch < 7 xs)) (newline)
(display (tsearch < 14 xs)) (newline)
(display (tsearch < 37 xs)) (newline)
(display (tsearch < 45 xs)) (newline)
(newline)
; no news is good news
(do ((x 1 (+ x 1))) ((= x 50) (display 'okay))
(assert (bsearch < x xs) (tsearch < x xs)))