🦀 Rust

خوارزميات البحث في Rust: دليل شامل

الدرس 30 / 35 • قراءة النظرية كاملة

Что это такое и зачем? (аналогия из реальной жизни)

Представь, что ты потерял ключи от дома в огромной куче игрушек в своей комнате. Как ты их ищешь? Ты можешь перебирать игрушку за игрушкой, пока не наткнешься на ключи. А если ты знаешь, что ключи металлические, ты можешь взять магнит и быстро проверить все игрушки подряд. Или, если ты вчера точно помнишь, что играл с ключами возле письменного стола, ты сразу пойдешь искать туда.

В программировании мы постоянно ищем данные: нужно найти пользователя по имени в списке, проверить, есть ли товар в корзине, или отыскать самую высокую температуру за неделю. Алгоритмы поиска — это те самые способы, которыми компьютер находит нужную информацию. Без них программы были бы слепыми и медленными, как человек, который ищет иголку в стоге сена вслепую.

💡 Простая мысль: Алгоритм поиска — это инструкция для компьютера: "Как именно ты будешь искать то, что я прошу?"

В этой статье мы разберем два самых важных алгоритма поиска на языке Rust: линейный поиск (простой перебор) и бинарный поиск (умный поиск в отсортированных данных). Ты узнаешь, когда какой применять, как писать код без ошибок и почему Rust делает поиск особенно безопасным.

Теория: как это работает изнутри

Линейный поиск (Linear Search)

Как работает: Представь, что ты читаешь список учеников в журнале с первой строчки до последней. Ты смотришь на каждое имя и спрашиваешь: "Это Вася?". Если да — ты нашел. Если нет — идешь дальше. Если дошел до конца и не нашел — значит, Васи в списке нет.

Это самый простой и универсальный алгоритм. Ему всё равно, как расположены данные: вперемешку, по алфавиту или по дате рождения. Он просто идет по порядку.

Сложность: В худшем случае (если элемент последний или его нет) придется проверить все N элементов. Поэтому говорят, что сложность алгоритма — O(n) (читается "О от n"). Чем больше данных, тем дольше поиск.

Бинарный поиск (Binary Search)

Как работает: А теперь представь, что журнал учеников отсортирован по алфавиту. Ты открываешь его примерно посередине. Видишь букву "Л". Тебе нужен "Сидоров". Ты понимаешь: "С" идет после "Л", значит, Сидоров точно во второй половине журнала. Первую половину можно выбросить! Ты снова открываешь середину оставшейся части, смотришь, и так повторяешь, пока не найдешь фамилию или не поймешь, что её нет.

Каждый шаг алгоритма отбрасывает половину данных! Это невероятно быстро.

Сложность: O(log n) (логарифмическая сложность). Если у тебя 1000 элементов, линейный поиск в худшем случае сделает 1000 проверок. Бинарный — всего 10 (потому что 2¹⁰ ≈ 1000). Для миллиона элементов разница будет 1 000 000 против 20 проверок.

⚠️ Важнейшее условие: Бинарный поиск работает ТОЛЬКО на отсортированных данных. Если массив не отсортирован, бинарный поиск выдаст мусор или не найдет то, что есть.

Синтаксис в Rust: все формы и варианты

Rust — язык системный и строгий. Он не прощает ошибок с памятью, но зато дает мощные инструменты для работы с данными. Рассмотрим, как реализовать оба алгоритма.

Базовая структура: срезы (slices)

В Rust мы чаще всего работаем не с целыми массивами, а со срезами (&[T]). Это "окошко" в массив, которое знает свою длину. Срезы безопасны: компилятор проверяет, что мы не выйдем за границы.

Линейный поиск: три варианта

Способ	Описание	Когда использовать
`for element in slice`	Ручной перебор с циклом	Когда нужно делать что-то особенное во время поиска
`slice.iter().position()`	Встроенный метод, возвращает индекс	Стандартный случай, нужно только найти позицию
`slice.contains()`	Проверка наличия (да/нет)	Нужно только узнать, есть ли элемент

Бинарный поиск: стандартная библиотека

Rust уже содержит готовый бинарный поиск в стандартной библиотеке! Его не нужно писать с нуля (хотя мы напишем для понимания).

Метод	Что возвращает	Пример
`slice.binary_search(&value)`	`Result<usize, usize>` Ok(индекс) — нашли Err(индекс_вставки) — не нашли	`let arr = [1,3,5]; arr.binary_search(&3) // Ok(1)`
`slice.binary_search_by()`	То же, но с кастомной функцией сравнения	Для поиска по структурам
`slice.binary_search_by_key()`	Поиск по ключу (например, по полю структуры)	`people.binary_search_by_key(&"Alice", \|p\| p.name)`

Примеры кода — от простого к сложному

Пример 1: Линейный поиск вручную (самый простой)

// Функция линейного поиска
// Принимает срез чисел и число для поиска
// Возвращает Option<usize> — индекс или None
fn linear_search(numbers: &[i32], target: i32) -> Option<usize> {
    // Перебираем все элементы по индексу
    for i in 0..numbers.len() {
        // Если нашли совпадение — возвращаем индекс
        if numbers[i] == target {
            return Some(i);
        }
    }
    // Если ничего не нашли — возвращаем None
    None
}

fn main() {
    let data = [10, 20, 30, 40, 50];
    let target = 30;
    
    match linear_search(&data, target) {
        Some(index) => println!("Нашли {} на позиции {}", target, index),
        None => println!("{} не найден", target),
    }
    // Вывод: Нашли 30 на позиции 2
}

Пример 2: Линейный поиск с помощью итератора

fn main() {
    let fruits = ["яблоко", "банан", "вишня", "дыня"];
    let search_for = "вишня";
    
    // position() — встроенный метод итератора
    // Он возвращает Option<usize>
    let result = fruits.iter().position(|&fruit| fruit == search_for);
    
    match result {
        Some(index) => println!("'{}' найден на индексе {}", search_for, index),
        None => println!("'{}' не найден", search_for),
    }
    // Вывод: 'вишня' найден на индексе 2
}

Пример 3: Поиск с проверкой наличия (contains)

fn main() {
    let grades = [85, 92, 78, 90, 88];
    let check_grade = 100;
    
    // contains() возвращает bool — есть или нет
    if grades.contains(&check_grade) {
        println!("Оценка {} есть в списке!", check_grade);
    } else {
        println!("Оценки {} нет в списке.", check_grade);
    }
    // Вывод: Оценки 100 нет в списке.
}

Пример 4: Бинарный поиск (ручная реализация)

// Ручная реализация бинарного поиска
// Работает ТОЛЬКО на отсортированном массиве!
fn binary_search_manual(arr: &[i32], target: i32) -> Option<usize> {
    // Левая и правая границы поиска
    let mut left = 0;
    let mut right = arr.len(); // right — это "за последним элементом"
    
    while left < right {
        // Находим середину (безопасно, без переполнения)
        let mid = left + (right - left) / 2;
        
        if arr[mid] == target {
            return Some(mid); // Нашли!
        } else if arr[mid] < target {
            left = mid + 1; // Ищем в правой половине
        } else {
            right = mid; // Ищем в левой половине
        }
    }
    None // Не нашли
}

fn main() {
    let sorted = [2, 5, 8, 12, 16, 23, 38, 45, 56, 67];
    let target = 23;
    
    match binary_search_manual(&sorted, target) {
        Some(i) => println!("Нашли {} на индексе {}", target, i),
        None => println!("{} не найден", target),
    }
    // Вывод: Нашли 23 на индексе 5
}

Пример 5: Бинарный поиск из стандартной библиотеки

fn main() {
    let numbers = [1, 3, 5, 7, 9, 11, 13];
    
    // binary_search() возвращает Result
    // Ok(индекс) — элемент найден
    // Err(индекс_вставки) — элемент не найден, но можно вставить сюда
    match numbers.binary_search(&7) {
        Ok(index) => println!("Нашли 7 на позиции {}", index),
        Err(index) => println!("7 не найден, можно вставить на позицию {}", index),
    }
    // Вывод: Нашли 7 на позиции 3
    
    // Поиск отсутствующего элемента
    match numbers.binary_search(&4) {
        Ok(index) => println!("Нашли 4 на позиции {}", index),
        Err(index) => println!("4 не найден, можно вставить на позицию {}", index),
    }
    // Вывод: 4 не найден, можно вставить на позицию 2
}

Пример 6: Поиск в векторе структур

// Определяем структуру "Студент"
#[derive(Debug)]
struct Student {
    name: String,
    grade: u8,
}

fn main() {
    // Создаем вектор студентов (уже отсортирован по именам!)
    let mut students = vec![
        Student { name: "Анна".to_string(), grade: 5 },
        Student { name: "Борис".to_string(), grade: 4 },
        Student { name: "Виктор".to_string(), grade: 3 },
        Student { name: "Галина".to_string(), grade: 5 },
    ];
    
    // Сортируем на всякий случай (бинарный поиск требует сортировки)
    students.sort_by_key(|s| s.name.clone());
    
    // Ищем студента по имени с помощью binary_search_by_key
    let search_name = "Виктор";
    let result = students.binary_search_by_key(&search_name.to_string(), |s| s.name.clone());
    
    match result {
        Ok(index) => println!("Нашли: {:?}", students[index]),
        Err(_) => println!("Студент '{}' не найден", search_name),
    }
    // Вывод: Нашли: Student { name: "Виктор", grade: 3 }
}

Пример 7: Поиск всех вхождений (линейный поиск с коллекционированием)

fn find_all_occurrences(data: &[i32], target: i32) -> Vec<usize> {
    // Создаем пустой вектор для хранения индексов
    let mut indices = Vec::new();
    
    // Проходим по всем элементам с их индексами
    for (index, &value) in data.iter().enumerate() {
        if value == target {
            indices.push(index); // Добавляем индекс в результат
        }
    }
    indices // Возвращаем вектор индексов
}

fn main() {
    let scores = [10, 20, 10, 30, 10, 40];
    let target = 10;
    
    let positions = find_all_occurrences(&scores, target);
    println!("Число {} найдено на позициях: {:?}", target, positions);
    // Вывод: Число 10 найдено на позициях: [0, 2, 4]
}

Сравнение с Python: чем похоже и чем отличается

Аспект	Python	Rust
Линейный поиск (ручной)	`for i, val in enumerate(arr):`	`for (i, &val) in arr.iter().enumerate()`
Проверка наличия	`if x in arr:` (очень просто)	`arr.contains(&x)` (тоже просто, но с &)
Поиск индекса	`arr.index(x)` (вызывает исключение, если нет)	`arr.iter().position(\|&v\| v == x)` (возвращает Option)
Бинарный поиск	`bisect.bisect_left(arr, x)` (из модуля bisect)	`arr.binary_search(&x)` (встроенный метод)
Обработка отсутствия	Исключение ValueError (нужно ловить try/except)	Option или Result (нужно обрабатывать match)
Производительность	Медленнее (интерпретатор)	Быстрее (компилируемый, без накладных расходов)
Безопасность памяти	Автоматическая (сборщик мусора)	Статическая проверка на этапе компиляции

🔑 Главное отличие: В Rust ты всегда должен думать о том, что элемент может не найтись. Компилятор заставит тебя обработать оба случая (нашли / не нашли). В Python ты можешь "забыть" и получить ошибку во время работы программы.

Типичные ошибки и подводные камни

1. Забыл отсортировать массив для бинарного поиска

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

// ❌ Ошибка: массив не отсортирован
let unsorted = [5, 1, 3, 9, 2];
match unsorted.binary_search(&3) {
    Ok(i) => println!("Нашли на {}", i), // Может найти, а может и нет!
    Err(_) => println!("Не нашли"),
}

// ✅ Правильно: сначала сортируем
let mut sorted = unsorted.clone();
sorted.sort();
match sorted.binary_search(&3) {
    Ok(i) => println!("Нашли на {}", i),
    Err(_) => println!("Не нашли"),
}

2. Путаница с границами в ручном бинарном поиске

Очень легко ошибиться с условием while left < right или while left <= right. Это приводит к бесконечному циклу или пропуску элементов.

💡 Совет: Всегда используй готовый binary_search() из стандартной библиотеки. Он написан профессионалами и оттестирован.

3. Забыл про & (ссылку) при передаче в contains/binary_search

let arr = [1, 2, 3];
// ❌ Ошибка: нужно передавать ссылку
// arr.contains(2); // Не скомпилируется!
// ✅ Правильно:
arr.contains(&2); // Работает

4. Поиск в пустом массиве

Линейный поиск в пустом массиве просто ничего не найдет. Бинарный поиск тоже вернет Err(0). Это нормально, но новички иногда паникуют.

5. Использование линейного поиска на больших данных

Если у тебя 100 000 элементов и ты ищешь один — линейный поиск может быть очень медленным. Всегда думай: "Могу ли я отсортировать данные и использовать бинарный поиск?"

Лучшие практики и советы профессионалов

1. Всегда используй стандартную библиотеку

Rust предоставляет binary_search(), contains(), position(). Не пиши велосипед, если есть готовое решение. Код будет быстрее, безопаснее и понятнее другим.

2. Выбирай правильную структуру данных

Если тебе нужно часто искать — используй HashMap или BTreeMap. Они дают поиск за O(1) или O(log n) без необходимости сортировки.

use std::collections::HashMap;

fn main() {
    let mut phonebook = HashMap::new();
    phonebook.insert("Анна", "+7-123-456-78-90");
    phonebook.insert("Борис", "+7-098-765-43-21");
    
    // Поиск в HashMap — мгновенный!
    if let Some(phone) = phonebook.get("Анна") {
        println!("Телефон Анны: {}", phone);
    }
}

3. Используй итераторы и замыкания

Вместо ручных циклов с индексами используй iter(), position(), filter(). Это делает код более декларативным и менее подверженным ошибкам.

4. Всегда обрабатывай Option и Result

Не используй unwrap() в production-коде. Используй match или if let. Компилятор тебя не предупредит, но программа упадет в самый неподходящий момент.

5. Тестируй граничные случаи

Проверяй: пустой массив, массив из одного элемента, поиск первого элемента, поиск последнего, поиск отсутствующего элемента.

#[test]
fn test_binary_search() {
    let arr = [1, 3, 5, 7];
    assert_eq!(arr.binary_search(&1), Ok(0));  // Первый
    assert_eq!(arr.binary_search(&7), Ok(3));  // Последний
    assert_eq!(arr.binary_search(&4), Err(2)); // Отсутствует
    assert_eq!(arr.binary_search(&0), Err(0)); // Меньше всех
    assert_eq!(arr.binary_search(&9), Err(4)); // Больше всех
}

Вопросы для самопроверки

Вопрос: В чем главное отличие линейного поиска от бинарного?
Ответ: Линейный поиск проверяет элементы по порядку (сложность O(n)), бинарный — делит массив пополам на каждом шаге (сложность O(log n)), но требует отсортированных данных.
Вопрос: Почему бинарный поиск не работает на неотсортированном массиве?
Ответ: Потому что алгоритм принимает решение о том, в какой половине искать, на основе сравнения с серединой. Если данные не упорядочены, это решение будет неверным.
Вопрос: Что вернет binary_search, если элемент не найден?
Ответ: Err(index), где index — позиция, на которую можно вставить элемент, чтобы сохранить сортировку.
Вопрос: Какой метод использовать, если нужно только проверить наличие элемента (без индекса)?
Ответ: contains(). Он возвращает bool.
Вопрос: В чем разница между position() и binary_search()?
Ответ: position() — линейный поиск, работает на любых данных. binary_search() — бинарный поиск, требует сортировки, но работает быстрее.
Вопрос: Что произойдет, если вызвать binary_search на пустом срезе?
Ответ: Ничего страшного. Он сразу вернет Err(0), так как left (0) не меньше right (0).
Вопрос: Как найти все вхождения элемента в массиве?
Ответ: Использовать линейный поиск с фильтрацией: arr.iter().enumerate().filter(|(_, &v)| v == target).map(|(i, _)| i).collect().
Вопрос: Почему в Rust нужно передавать &value в contains и binary_search?
Ответ: Потому что эти методы принимают ссылку на значение, а не само значение. Это позволяет избежать копирования больших данных.
Вопрос: Какой алгоритм поиска выбрать для списка из 10 элементов? А для 10 миллионов?
Ответ: Для 10 элементов разница незаметна, можно использовать линейный. Для 10 миллионов — только бинарный (или HashMap).
Вопрос: Что быстрее: HashMap::get() или binary_search()?
Ответ: HashMap::get() в среднем O(1), binary_search() O(log n). Для больших данных HashMap обычно быстрее, но требует больше памяти.

Итог и что изучить дальше

Мы разобрали два фундаментальных алгоритма поиска — линейный и бинарный. Ты узнал:

Как они работают и в чем их сила
Как писать их на Rust разными способами
Какие готовые инструменты есть в стандартной библиотеке
Как избегать типичных ошибок
Как Rust отличается от Python в контексте поиска

Теперь ты можешь уверенно искать данные в массивах и векторах. Но это только начало!

Что изучить дальше:

Алгоритмы сортировки — бинарный поиск бесполезен без отсортированных данных. Изучи быструю сортировку (quicksort) и сортировку слиянием (merge sort).
Хеш-таблицы (HashMap) — поиск за O(1) — это магия. Пойми, как работают хеш-функции и коллизии.
Деревья поиска (BTreeMap) — Rust предлагает B-деревья, которые всегда отсортированы и поддерживают эффективный поиск.
Поиск в строках — алгоритмы Кнута-Морриса-Пратта (KMP) и Бойера-Мура для поиска подстроки в тексте.
Поиск в графах — BFS и DFS для навигации по сложным структурам данных.

🎯 Главный совет: Не пытайся запомнить все алгоритмы. Пойми принципы: "разделяй и властвуй" (бинарный поиск) и "полный перебор" (линейный поиск). Остальное — вариации на эти темы. Практикуйся, пиши код, и алгоритмы станут твоими верными помощниками!

← السابق خوارزميات الترتيب في Rust: دليل شامل التالي → أنماط التصميم في Rust: دليل شامل