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

*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):