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.
On Mon, 29 Mar 2004, David Van Horn wrote:
> [ 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
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: -)