On Mon, Apr 14, 2008 at 8:56 PM, Samium Gromoff _deepfire@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