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

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.

*To*: srfi-43@xxxxxxxxxxxxxxxxx*Subject*: Fwd: vector-binary-search*From*: David Van Horn <dvanhorn@xxxxxxxxxx>*Date*: Mon, 29 Mar 2004 23:47:12 -0500*Cc*: Sergei Egorov <esl@xxxxxxx>*Delivered-to*: srfi-43@xxxxxxxxxxxxxxxxx*User-agent*: Internet Messaging Program (IMP) 3.2.1

[ 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

**Follow-Ups**:**Re: Fwd: vector-binary-search***From:*campbell

- Prev by Date:
**re: Updates to near finalization (finally!)** - Next by Date:
**Re: VECTOR-UNFOLD and VECTOR-TABULATE** - Previous by thread:
**Re: VECTOR-UNFOLD and VECTOR-TABULATE** - Next by thread:
**Re: Fwd: vector-binary-search** - Index(es):