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

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

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

USING: binary-search.private kernel sequences ;

IN: binary-search

: search
    ( ... seq quot: ( ... elt -- ... <=> ) -- ... i elt )
    over empty?
    [ 2drop f f ] [ [ 0 over length ] dip (search) ] if ; inline