basis/binary-search/binary-search-docs.factor

   1 IN: binary-search
   2 USING: help.markup help.syntax sequences kernel math.order ;
   3
   4 HELP: search
   5 { $values { "seq" "a sorted sequence" } { "quot" { $quotation ( elt -- <=> ) } } { "i" "an index, or " { $link f } } { "elt" "an element, or " { $link f } } }
   6 { $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+ } ")."
   7 $nl
   8 "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+ } "."
   9 $nl
  10 "If the sequence is empty, outputs " { $link f } " " { $link f } "." }
  11 { $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 } "." }
  12 { $examples
  13     "Searching for an integer in a sorted array:"
  14     { $example
  15         "USING: binary-search kernel math.order prettyprint ;"
  16         "{ -130 -40 10 90 160 170 280 } [ 50 >=< ] search [ . ] bi@"
  17         "2\n10"
  18     }
  19     "Frequently, the quotation passed to " { $link search } " is constructed by " { $link curry } " or " { $link with } " in order to make the search key a parameter:"
  20     { $example
  21         "USING: binary-search kernel math.order prettyprint ;"
  22         "50 { -130 -40 10 90 160 170 280 } [ <=> ] with search [ . ] bi@"
  23         "2\n10"
  24     }
  25 } ;
  26
  27 { find find-from find-last find-last-from search } related-words
  28
  29 HELP: sorted-index
  30 { $values { "obj" object } { "seq" "a sorted sequence" } { "i" "an index, or " { $link f } } }
  31 { $description "Outputs the index of the element closest to " { $snippet "elt" } " in the sequence. See " { $link search } " for details." }
  32 { $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 } "." } ;
  33
  34 { index index-from last-index last-index-from sorted-index } related-words
  35
  36 HELP: sorted-member?
  37 { $values { "obj" object } { "seq" "a sorted sequence" } { "?" boolean } }
  38 { $description "Tests if the sorted sequence contains " { $snippet "elt" } ". Equality is tested with " { $link = } "." } ;
  39
  40 { member? sorted-member? } related-words
  41
  42 HELP: sorted-member-eq?
  43 { $values { "obj" object } { "seq" "a sorted sequence" } { "?" boolean } }
  44 { $description "Tests if the sorted sequence contains " { $snippet "elt" } ". Equality is tested with " { $link eq? } "." } ;
  45
  46 { member-eq? sorted-member-eq? } related-words
  47
  48 ARTICLE: "binary-search" "Binary search"
  49 "The " { $emphasis "binary search" } " algorithm allows elements to be located in sorted sequence in " { $snippet "O(log n)" } " time."
  50 { $subsections search }
  51 "Variants of sequence words optimized for sorted sequences:"
  52 { $subsections
  53     sorted-index
  54     sorted-member?
  55     sorted-member-eq?
  56 }
  57 { $see-also "order-specifiers" "sequences-sorting" } ;
  58
  59 ABOUT: "binary-search"