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