Fwd: vector-binary-search

[David Van Horn <dvanhorn@xxxxxxxxxx>]

[ The following is forwarded on behalf of Sergei Egorov <esl@xxxxxxx>.
  -- David ]

I think that using "compare" procedure for vector-binary-search
is not very convenient. There are two main sources of inconvenience:
first, there are no ready-to-use procedures implementing the "compare"
interface; second, in most cases vector-binary-search will be used
on vectors sorted by vector-sort{!} and in 90% of implementations
sort using "less" predicates returning boolean.

Binary search and sort procedures are closely related, so using the
same convention for ordering predicate will benefit both. Since SRFI-43
does not include any sorting procedures (I support this decision), it
would be better either to drop vector-binary-search altogether or
include a version which has a better chance to be compatible with
sorting procedures defined elsewhere:

(vector-binary-search vec val less)  => val position or #f

Here's an implementation that is compatible with traditional
use of "less" in sorting procedures:

(define (vector-binary-search vec obj less)
  (let search ((s 0) (e (vector-length vec)))
    (let ((len (- e s)))
      (case len
        ((0) 
         #f)
        ((1) 
         (let ((x (vector-ref vec s)))
           (if (or (less x obj) (less obj x)) 
               #f
               s)))
        (else
         (let ((i (+ s (quotient len 2))))
           (let ((x (vector-ref vec i)))
             (cond
               ((less obj x) (search s i))
               ((less x obj) (search (+ i 1) e))
               (else i)))))))))

-- Sergei