search ( seq quot: ( elt -- <=> ) -- i elt )
Factor handbook > The language > Collections > Sequence operations > Binary search

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


Vocabulary
binary-search

Inputs and outputs
seqa sorted sequence
quota quotation with stack effect ( elt -- <=> )
ian index, or f
eltan 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

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


See also
find, find-from, find-last, find-last-from

Definition