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