Email list hosting service & mailing list manager

Fwd: vector-binary-search David Van Horn (30 Mar 2004 04:47 UTC)
Re: Fwd: vector-binary-search campbell@xxxxxx (31 Mar 2004 21:01 UTC)

Re: Fwd: vector-binary-search campbell@xxxxxx 30 Mar 2004 21:24 UTC

On Mon, 29 Mar 2004, David Van Horn wrote:

> [ The following is forwarded on behalf of Sergei Egorov <xxxxxx@acm.org>.
>   -- 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

I kinda like having VECTOR-BINARY-SEARCH...

> 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

...but I'm not sure this is a good idea, either: it doesn't make much
of a difference if you just use integers, but what if you, for example,
use strings instead?  You end up performing a _huge_ number of extra,
unnecessary comparisons of the entire string.  Instead, with a three-
way comparator, for each iteration, there is only one entire string
comparison (and a number of integer or symbol comparisons).  Moreover,
as Olin Shivers pointed out on the SRFI 32 mailing list, there _are_
some sorting algorithms that benefit from three-way comparators; my
VECTOR-BINARY-SEARCH isn't alone with three-way comparators.  So I'd
like to stick with the interface as it is.  (By the way, for searching
vectors of integers, there _is_ a convenient comparator: -)