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