(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
    :> midpoint to from - 1 <=
    [ midpoint@ midpoint ] [
        midpoint quot call {
            { +lt+ [ seq from midpoint@ quot (search) ] }
            { +gt+ [ seq midpoint@ to quot (search) ] }
            { +eq+ [ midpoint@ midpoint ] }
        } case
    ] if ; inline recursive