Function slice_group_by::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 slice_group_by::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, });