[−][src]Function sdset::exponential_search_by_key
pub fn exponential_search_by_key<T, B, F>(
slice: &[T],
b: &B,
f: F
) -> Result<usize, usize> where
F: FnMut(&T) -> B,
B: Ord,
Binary searches this sorted slice with a key extraction function.
Assumes that the slice is sorted by the key.
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_key; let s = &[(0, 0), (2, 1), (4, 1), (5, 1), (3, 1), (1, 2), (2, 3), (4, 5), (5, 8), (3, 13), (1, 21), (2, 34), (4, 55)]; assert_eq!(exponential_search_by_key(s, &13, |&(a,b)| b), Ok(9)); assert_eq!(exponential_search_by_key(s, &4, |&(a,b)| b), Err(7)); assert_eq!(exponential_search_by_key(s, &100, |&(a,b)| b), Err(13)); let r = exponential_search_by_key(s, &1, |&(a,b)| b); assert!(match r { Ok(1..=4) => true, _ => false, });