core/binary-search/binary-search-docs.factor

   1 IN: binary-search
   2 USING: help.markup help.syntax sequences kernel math.order ;
   3
   4 ARTICLE: "binary-search" "Binary search"
   5 "The " { $emphasis "binary search" } " algorithm allows elements to be located in sorted sequence in " { $snippet "O(log n)" } " time."
   6 { $subsection search }
   7 "Variants of sequence words optimized for sorted sequences:"
   8 { $subsection sorted-index }
   9 { $subsection sorted-member? }
  10 { $subsection sorted-memq? }
  11 { $see-also "order-specifiers" "sequences-sorting" } ;
  12
  13 ABOUT: "binary-search"
  14
  15 HELP: search
  16 { $values { "seq" "a sorted sequence" } { "quot" "a quotation with stack effect " { $snippet "( elt -- <=> )" } } { "i" "an index, or " { $link f } } { "elt" "an element, or " { $link f } } }
  17 { $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+ } ")."
  18 $nl
  19 "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, least element for which the quotation output " { $link +lt+ } "."
  20 $nl
  21 "If the sequence is empty, outputs " { $link f } " " { $link f } "." }
  22 { $notes "If the sequence has at least one element, this word always outputs a valid index, because it finds the closest match, not necessarily an exact one. In this respect its behavior differs from " { $link find } "." } ;
  23
  24 { find find-from find-last find-last find-last-from search } related-words
  25
  26 HELP: sorted-index
  27 { $values { "elt" object } { "seq" "a sorted sequence" } { "i" "an index, or " { $link f } } { "elt" "an element, or " { $link f } } }
  28 { $description "Outputs the index and value of the element closest to " { $snippet "elt" } " in the sequence. See " { $link search } " for details." }
  29 { $notes "If the sequence has at least one element, this word always outputs a valid index, because it finds the closest match, not necessarily an exact one. In this respect its behavior differs from " { $link index } "." } ;
  30
  31 { index index-from last-index last-index-from sorted-index } related-words
  32
  33 HELP: sorted-member?
  34 { $values { "elt" object } { "seq" "a sorted sequence" } { "?" "a boolean" } }
  35 { $description "Tests if the sorted sequence contains " { $snippet "elt" } ". Equality is tested with " { $link = } "." } ;
  36
  37 { member? sorted-member? } related-words
  38
  39 HELP: sorted-memq?
  40 { $values { "elt" object } { "seq" "a sorted sequence" } { "?" "a boolean" } }
  41 { $description "Tests if the sorted sequence contains " { $snippet "elt" } ". Equality is tested with " { $link eq? } "." } ;
  42
  43 { memq? sorted-memq? } related-words