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

Vocabulary

binary-search.private

Inputs

seq	an object
from	an object
to	an object
quot	a quotation with stack effect ( ... elt -- ... <=> )

Outputs

i	an object
elt	an object

Definition

USING: combinators kernel math math.order sequences.private ;

IN: binary-search.private

:: (search)
    ( ... seq from to quot: ( ... elt -- ... <=> ) -- ... i elt )
    from to + 2/ :> midpoint midpoint seq nth-unsafe
    :> elt to from - 1 <=
    [ midpoint elt ] [
        elt quot call {
            { +lt+ [ seq from midpoint quot (search) ] }
            { +gt+ [ seq midpoint to quot (search) ] }
            { +eq+ [ midpoint elt ] }
        } case
    ] if ; inline recursive