### 3 releases

0.1.2 | May 8, 2021 |
---|---|

0.1.1 | Oct 30, 2018 |

0.1.0 | Oct 30, 2018 |

#**855** in Data structures

**1,376** downloads per month

Used in **4** crates
(3 directly)

**MIT**license

5KB

81 lines

# binary-search

Given a monotone function, find the largest quantity that is too small
and the smallest quantity that is too large. The first two arguments to

set the bounds of the search space.`binary_search`

`use` `binary_search``::``{`binary_search`,` Direction`}``;`
`fn` `main``(``)`` ``{`
`let` values `=`
`[``0``,` `4``,` `5``,` `6``,` `7``,` `9``,` `456``]``;`
`let` `(`largest_low`,` smallest_high`)` `=`
`binary_search``(``(``0``,` `(``)``)``,` `(`values`.``len``(``)``,` `(``)``)``,` `|``i``|`
`if` values`[`i`]` `<` `6` `{`
`Direction``::`Low`(``(``)``)`
`}` `else` `{`
`Direction``::`High`(``(``)``)`
`}`
`)``;`
`dbg!``(`largest_low`)``;`
`dbg!``(`smallest_high`)``;`
`}`

You can also provide an associated 'witness' as in this
example. Witnesses are passed in as well as produced from

. The arguments act as a proof that the function does
indeed transition within the range. If you don't know that this is the
case, you may need to call your function at the bounds first.`binary_search`

`use` `binary_search``::``{`binary_search`,` Direction`}``;`
`fn` `main``(``)`` ``{`
`let` values `=`
`[``Ok``(``"`foo`"``)``,` `Ok``(``"`bar`"``)``,` `Ok``(``"`baz`"``)``,` `Err``(``false``)``,` `Err``(``true``)``]``;`
`let` `(`largest_low`,` smallest_high`)` `=`
`binary_search``(``(``0``,` `"`foo`"``)``,` `(`values`.``len``(``)` `-` `1``,` `true``)``,` `|``i``|`
`match` values`[`i`]` `{`
`Ok``(`x`)` `=>` `Direction``::`Low`(`x`)``,`
`Err``(`x`)` `=>` `Direction``::`High`(`x`)``,`
`}`
`)``;`
`dbg!``(`largest_low`)``;` `//` "baz"
`dbg!``(`smallest_high`)``;` `//` false
`}`