Двоичный поиск – это фундаментальный алгоритм, используемый для поиска в отсортированных коллекциях. Он предлагает эффективный способ найти определенное значение в отсортированном массиве или списке путем многократного деления пространства поиска пополам. В этой статье мы рассмотрим различные методы реализации бинарного поиска в Rust, а также приведем примеры кода.

Метод 1: Рекурсивный двоичный поиск
Rust позволяет нам реализовать двоичный поиск, используя рекурсивный подход. Вот пример реализации:

fn binary_search_recursive<T: Ord>(arr: &[T], target: &T) -> Option<usize> {
    let (left, right) = (0, arr.len() - 1);
    binary_search_recursive_helper(arr, target, left, right)
}
fn binary_search_recursive_helper<T: Ord>(arr: &[T], target: &T, left: usize, right: usize) -> Option<usize> {
    if left > right {
        return None;
    }
    let mid = left + (right - left) / 2;
    match arr[mid].cmp(target) {
        std::cmp::Ordering::Less => binary_search_recursive_helper(arr, target, mid + 1, right),
        std::cmp::Ordering::Greater => binary_search_recursive_helper(arr, target, left, mid - 1),
        std::cmp::Ordering::Equal => Some(mid),
    }
}

Метод 2: итеративный двоичный поиск
В качестве альтернативы двоичный поиск можно реализовать с использованием итеративного подхода. Этот метод использует цикл для многократного обновления границ поиска до тех пор, пока не будет найдено целевое значение или пока пространство поиска не будет исчерпано. Вот пример реализации:

fn binary_search_iterative<T: Ord>(arr: &[T], target: &T) -> Option<usize> {
    let (mut left, mut right) = (0, arr.len() - 1);
    while left <= right {
        let mid = left + (right - left) / 2;
        match arr[mid].cmp(target) {
            std::cmp::Ordering::Less => left = mid + 1,
            std::cmp::Ordering::Greater => right = mid - 1,
            std::cmp::Ordering::Equal => return Some(mid),
        }
    }
    None
}

Метод 3: использование функции slice::binary_search
Rust предоставляет встроенную функцию binary_searchдля срезов, которая выполняет двоичный поиск и возвращает индекс найденного элемента.. Вот пример использования:

fn binary_search_builtin<T: Ord>(arr: &[T], target: &T) -> Option<usize> {
    arr.binary_search(target).ok()
}

Двоичный поиск – это мощный алгоритм для эффективного поиска в отсортированных коллекциях. В этой статье мы исследовали три различных метода реализации бинарного поиска в Rust: рекурсивный бинарный поиск, итеративный бинарный поиск и использование встроенной функции binary_search. Каждый метод имеет свои преимущества и может использоваться в зависимости от конкретных требований и предпочтений вашего проекта.

Используя двоичный поиск, вы можете значительно улучшить производительность поиска в своих приложениях Rust при работе с отсортированными данными.