#[cfg(test)]
mod tests;
pub fn binary_search_slice<E, K>(data: &'d [E], key_fn: impl Fn(&E) -> K, key: &K) -> &'d [E]
where
K: Ord,
{
let mid = match data.binary_search_by_key(key, &key_fn) {
Ok(mid) => mid,
Err(_) => return &[],
};
let size = data.len();
let mut start = mid;
let mut previous = mid;
let mut step = 1;
loop {
start = start.saturating_sub(step);
if start == 0 || key_fn(&data[start]) != *key {
break;
}
previous = start;
step *= 2;
}
step = previous - start;
while step > 1 {
let half = step / 2;
let mid = start + half;
if key_fn(&data[mid]) != *key {
start = mid;
}
step -= half;
}
if start < size && key_fn(&data[start]) != *key {
start += 1;
}
let mut end = mid;
let mut previous = mid;
let mut step = 1;
loop {
end = end.saturating_add(step).min(size);
if end == size || key_fn(&data[end]) != *key {
break;
}
previous = end;
step *= 2;
}
step = end - previous;
while step > 1 {
let half = step / 2;
let mid = end - half;
if key_fn(&data[mid]) != *key {
end = mid;
}
step -= half;
}
&data[start..end]
}