[alexandria-devel] BISECT

[Nikodemus Siivola]

On Mon, Apr 14, 2008 at 8:56 PM, Samium Gromoff
<_deepfire at feelingofgreen.ru> wrote:
>
> Good day list,
>
> I believe the code below might meet the conservative standards of Alexandria.
>
> What do you think?
>
> (defun bisect (test n &optional (base 0))
>  "Find, using bisection, the largest positive integer below N and above,
>   or equal to BASE, which satisfies TEST of one argument.
>   Assumes monotonous truth value of TEST."

I can't claim I have thought this thru, but I the interface seems a
bit strange to me. I would have thought that something like the
following would be a more natural, and maybe even a more flexible
approach:

function BISECT value sequence &key start end key

Binary search for VALUE in SEQUENCE. KEY must return a monotonically
increasing real value for all elements of SEQUENCE: if I > J, then
(FUNCALL KEY (ELT SEQUENCE I)) > (FUNCALL KEY (ELT SEQUENCE J)).
Values obtained by KEY are compared against VALUE, and the element is
considered to match if all earlier elements in the sequence are
smaller then VALUE, and all later elements are greater.

...that's not quite right either: it doesn't say if the return value
is the element or the index (or both), it doesn't describe START and
END, and the later/earlier language is a bit vague.

But speaking in the abstract, I think BISECT / BINARY-SEARCH is within
the scope of Alexandria. Sorry for the slow reply.

Cheers,

 -- Nikodemus