Метод binary_search
Метод binary_search выполняет бинарный поиск
значения в отсортированном срезе. Он работает
только с отсортированными данными и возвращает
значение типа Result. Если элемент найден,
возвращается Ok с индексом найденного
элемента. Если элемент не найден, возвращается
Err с индексом, по которому элемент можно
вставить, чтобы сохранить порядок сортировки.
Параметром метод принимает значение, которое
нужно найти.
Важно: срез должен быть отсортирован по возрастанию, иначе результат работы метода не определён.
Синтаксис
slice.binary_search(&value)
Пример
Давайте найдём число 3 в отсортированном
срезе [1, 2, 3, 4, 5]:
fn main()
{
let arr = [1, 2, 3, 4, 5];
let res = arr.binary_search(&3);
println!("{:?}", res);
}
Результат выполнения кода:
Ok(2)
Пример
Давайте попробуем найти число 6,
которого нет в срезе [1, 2, 3, 4, 5]:
fn main()
{
let arr = [1, 2, 3, 4, 5];
let res = arr.binary_search(&6);
println!("{:?}", res);
}
Результат выполнения кода:
Err(5)
Число 6 можно вставить по индексу 5,
чтобы срез остался отсортированным.
Пример
Давайте найдём строку "c" в отсортированном
срезе строк ["a", "b", "c", "d", "e"]:
fn main()
{
let arr = ["a", "b", "c", "d", "e"];
let res = arr.binary_search(&"c");
println!("{:?}", res);
}
Результат выполнения кода:
Ok(2)
Пример
Давайте используем результат поиска для вставки отсутствующего элемента в нужную позицию:
fn main()
{
let mut arr = vec![1, 2, 3, 4, 5];
match arr.binary_search(&4) {
Ok(pos) => println!("found at {}", pos),
Err(pos) => arr.insert(pos, 4),
}
println!("{:?}", arr);
}
Результат выполнения кода:
found at 3
[1, 2, 3, 4, 5]
