USING: help.markup help.syntax sequences kernel math.order ;
HELP: search
-{ $values { "seq" "a sorted sequence" } { "quot" { $quotation ( elt -- <=> ) } } { "i" "an index, or " { $link f } } { "elt" "an element, or " { $link f } } }
+{ $values { "seq" "a sorted sequence" } { "quot" { $quotation ( ... elt -- ... <=> ) } } { "i" "an index, or " { $link f } } { "elt" "an element, or " { $link f } } }
{ $description "Performs a binary search on a sequence, calling the quotation to decide whether to end the search (" { $link +eq+ } "), search lower (" { $link +lt+ } ") or search higher (" { $link +gt+ } ")."
$nl
"If the sequence is non-empty, outputs the index and value of the closest match, which is either an element for which the quotation output " { $link +eq+ } ", or failing that, the least element for which the quotation output " { $link +lt+ } ", or if there were none of the above, the greatest element for which the quotation output " { $link +gt+ } "."
<PRIVATE
-:: (search) ( seq from to quot: ( elt -- <=> ) -- i elt )
+:: (search) ( ... seq from to quot: ( ... elt -- ... <=> ) -- ... i elt )
from to + 2/ :> midpoint@
midpoint@ seq nth-unsafe :> midpoint
PRIVATE>
-: search ( seq quot: ( elt -- <=> ) -- i elt )
+: search ( ... seq quot: ( ... elt -- ... <=> ) -- ... i elt )
over empty? [ 2drop f f ] [ [ 0 over length ] dip (search) ] if ; inline
GENERIC: natural-search ( obj seq -- i elt )