[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Fwd: vector-binary-search

This page is part of the web mail archives of SRFI 43 from before July 7th, 2015. The new archives for SRFI 43 contain all messages, not just those from before July 7th, 2015.

[ 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
         (let ((x (vector-ref vec s)))
           (if (or (less x obj) (less obj x)) 
         (let ((i (+ s (quotient len 2))))
           (let ((x (vector-ref vec i)))
               ((less obj x) (search s i))
               ((less x obj) (search (+ i 1) e))
               (else i)))))))))

-- Sergei