binary_search_slice using partition_point

binary_search_slice.rs

pub fn binary_search_slice_new<'d, E, K>(data: &'d [E], key_fn: impl Fn(&E) -> K, key: &K) -> &'d [E]
where
    K: Ord,
{
    let size = data.len();
    let start = data.partition_point(|x| key_fn(x) < *key);
    // At this point `start` either points at the first entry with equal or
    // greater key or is equal to `size` in case all elements have smaller keys
    // Invariant: start == size || key_fn(&data[start]) >= *key
    if start == size || key_fn(&data[start]) != *key {
        return &[];
    };
    // Invariant: start < size && key_fn(&data[start]) == *key

    // Find the first entry with key > `key`. Skip `start` entries since
    // key_fn(&data[start]) == *key
    // Invariant: offset == size ||  key_fn(&data[offset]) >= *key
    let offset = start + 1;
    let end = data[offset..].partition_point(|x| key_fn(x) <= *key) + offset;
    // Invariant: end == size || key_fn(&data[end]) > *key

    &data[start..end]
}