[−][src]Function sdset::exponential_search_by
pub fn exponential_search_by<T, F>(slice: &[T], f: F) -> Result<usize, usize> where
F: FnMut(&T) -> Ordering,
Binary searches this sorted slice with a comparator function.
The comparator function should implement an order consistent with the sort order of
the underlying slice, returning an order code that indicates whether its argument
is Less
, Equal
or Greater
the desired target.
If the value is found then Ok
is returned, containing the index of the matching element;
if the value is not found then Err
is returned, containing the index where a matching element
could be inserted while maintaining sorted order.
Examples
Looks up a series of four elements. The first is found, with a
uniquely determined position; the second and third are not
found; the fourth could match any position in [1, 4]
.
use sdset::exponential_search_by; let s = &[0, 1, 1, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55]; let seek = 13; assert_eq!(exponential_search_by(s, |probe| probe.cmp(&seek)), Ok(9)); let seek = 4; assert_eq!(exponential_search_by(s, |probe| probe.cmp(&seek)), Err(7)); let seek = 100; assert_eq!(exponential_search_by(s, |probe| probe.cmp(&seek)), Err(13)); let seek = 1; let r = exponential_search_by(s, |probe| probe.cmp(&seek)); assert!(match r { Ok(1..=4) => true, _ => false, });