Vocabulary

binary-search.private

Inputs and outputs

Definition

binary-search.private

Inputs and outputs

seq | an object |

from | an object |

to | an object |

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

i | an object |

elt | an object |

Definition

:: (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

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