Function binary_search 

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>,

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, ())))