binary_search

Function binary_search

Source 
pub fn binary_search<X, A, B, F>(
    low: (X, A),
    high: (X, B),
    f: F,
) -> ((X, A), (X, B))
where
    X: Betweenable,
    F: FnMut(X) -> Direction<A, B>,
Expand description

Perform a binary search within the specified bounds.

Given a monotone function, find the largest quantity that is too small and the smallest quantity that is too large.

A user-specified function will be called to determine whether or not an entry is considered lower or higher.

§Generics

  • X - the type of the search space. used to specify the bounds of the search and is used for the returned largest_low and smallest_high values.
  • A - the type for the low witness.
  • B - the type for the high witness.

§Arguments

§low

A tuple specifying the lower bound of the search.

Expanded as (lower_bound, witness) here for brevity.

  • lower_bound: X - the lower bound of the search space.\
  • witness: A - a value passed to the provided function that can be used to verify whether or not a transition is valid.

§high

A tuple specifying the upper bound of the search.

Expanded as (upper_bound, witness) here for brevity.

  • upper_bound: X - the upper bound of the search space.\
  • witness: B - a value passed to the provided function that can be used to verify whether or not a transition is valid.

§f

A FnMut(X) function that is called to evaluate each candidate transition point.

§Arguments
  • X - the current candidate transition point.
§Returns
  • Direction - whether the current candidate transition point is lower or higher than the search target.

§Return value

Returns a tuple ((largest_low: X, low_witness: A), (smallest_high: X, high_witness: B)).

  • largest_low: X - the largest value that the provided function indicated was Low.

  • low_witness: A - the witness value that the provided function last returned inside the Direction::Low.

  • smallest_high: X - the smallest value that the provided function indicated was High.

  • high_witness: B - the witness value that the provided function last returned inside the Direction::High.

§Examples

use binary_search::{binary_search, Direction};
let result = binary_search((1 as usize, ()), (100, ()), |x| {
if x < 23 {
	Direction::Low(())
} else {
	Direction::High(())
}
});
assert_eq!(result, ((22, ()), (23, ())))