search ( seq quot: ( elt -- <=> ) -- i elt )

Factor handbook » The language » Collections » Sequence operations » Binary search

Factor handbook » The language » Collections » Sequence operations » Binary search

Next: | sorted-index ( obj seq -- i ) |

Vocabulary

binary-search

Inputs

Outputs

Word description

Performs a binary search on a sequence, calling the quotation to decide whether to end the search ( +eq+ ), search lower ( +lt+ ) or search higher ( +gt+ ).

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 +eq+, or failing that, the least element for which the quotation output +lt+, or if there were none of the above, the greatest element for which the quotation output +gt+.

If the sequence is empty, outputs f f.

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 find.

Examples

Searching for an integer in a sorted array:

Frequently, the quotation passed to search is constructed by curry or with in order to make the search key a parameter:

See also

find, find-from, find-last, find-last-from

Definition

binary-search

Inputs

seq | a sorted sequence |

quot | a quotation with stack effect ( elt -- <=> ) |

Outputs

i | an index, or f |

elt | an element, or f |

Word description

Performs a binary search on a sequence, calling the quotation to decide whether to end the search ( +eq+ ), search lower ( +lt+ ) or search higher ( +gt+ ).

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 +eq+, or failing that, the least element for which the quotation output +lt+, or if there were none of the above, the greatest element for which the quotation output +gt+.

If the sequence is empty, outputs f f.

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 find.

Examples

Searching for an integer in a sorted array:

USING: binary-search kernel math.order prettyprint ;
{ -130 -40 10 90 160 170 280 } [ 50 >=< ] search [ . ] bi@

2 10

2 10

Frequently, the quotation passed to search is constructed by curry or with in order to make the search key a parameter:

USING: binary-search kernel math.order prettyprint ;
50 { -130 -40 10 90 160 170 280 } [ <=> ] with search [ . ] bi@

2 10

2 10

See also

find, find-from, find-last, find-last-from

Definition