;;; Binary search


(module binary-search (binary-search)

  (import scheme (chicken base) (chicken bitwise))

  (define (binary-search seq proc)
    (let-values (((seq len)
                  (cond ((pair? seq)
                         (let ((seq (list->vector seq)))
                           (values seq (vector-length seq))))
                        ((vector? seq)
                         (values seq (vector-length seq)))
                        ((integer? seq) (values #f seq))
                        (else (error 'binary-search "invalid sequence" seq)))))
      (and (> len 0)
           (let loop ((ps 0)
                      (pe len) )
             (let ((p (+ ps (arithmetic-shift (- pe ps) -1))))
               (let* ((x (if seq (##sys#slot seq p) p))
                      (r (proc x)) )
                 (cond ((= r 0) p)
                       ((< r 0)
                        (and (not (= pe p)) (loop ps p)))
                       (else (and (not (= ps p))
                                  (loop p pe))) ) ) ) ) ) ) )

  )