Suchalgorithmen in Swift: Eine ausführliche Anleitung

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

Представь, что ты потерял ключи от дома в своей комнате. Комната — это массив данных (например, список из 100 предметов). Твоя задача — найти ключи. Как ты будешь искать?

Первый способ: ты начинаешь осматривать каждый предмет по порядку: подушку, книгу, ручку, зарядку... Пока не наткнёшься на ключи. Это называется линейный поиск — самый простой и понятный метод.

Второй способ: если твоя комната идеально прибрана, и все вещи разложены по полочкам в алфавитном порядке (ключи лежат между «к» и «л»), ты можешь открыть шкаф посередине, посмотреть, с какой буквы начинаются вещи, и отбросить половину шкафа. Затем повторить. Это бинарный поиск — он работает только в упорядоченном пространстве, но в 100 раз быстрее.

Третий способ: если ты знаешь, что ключи — металлические, ты можешь использовать магнит. Это поиск по хешу — мгновенный доступ к данным, если знаешь их «отпечаток».

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

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

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

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

Суть: проходим по всем элементам массива по очереди, пока не найдём нужный.

• Сложность: O(n) — в худшем случае нужно проверить все элементы.
• Когда использовать: массив маленький (до 1000 элементов) или данные не отсортированы.
• Плюсы: не требует сортировки, работает с любыми типами данных.
• Минусы: медленный на больших объёмах.

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

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

• Сложность: O(log n) — при каждом шаге область поиска уменьшается вдвое.
• Когда использовать: массив большой и отсортирован.
• Плюсы: невероятно быстрый (для массива из 1 млн элементов нужно всего ~20 шагов).
• Минусы: требует предварительной сортировки.

3. Поиск по словарю (Dictionary/Hash Search)

Суть: используем хеш-таблицу (Dictionary в Swift), где каждый элемент хранится по уникальному ключу. Доступ к значению — мгновенный.

• Сложность: O(1) — константное время.
• Когда использовать: нужен быстрый доступ по ключу (например, поиск пользователя по ID).
• Плюсы: молниеносный поиск.
• Минусы: занимает больше памяти, ключи должны быть уникальными.

⚠️ Важное замечание: В Swift есть встроенные методы firstIndex(of:) и contains(_:), которые используют линейный поиск. Но понимание того, как они работают «под капотом», отличает настоящего разработчика от копировщика кода.

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

Swift предоставляет несколько способов реализации каждого алгоритма. Рассмотрим их все.

Линейный поиск

Бинарный поиск

Поиск по словарю

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

Пример 1: Линейный поиск — ручная реализация

// Простейшая функция линейного поиска
// Возвращает индекс элемента или nil, если элемент не найден
func linearSearch(in array: [T], target: T) -> Int? {
    // Проходим по всем элементам массива
    for (index, element) in array.enumerated() {
        // Сравниваем текущий элемент с искомым
        if element == target {
            return index  // Нашли — возвращаем индекс
        }
    }
    return nil  // Не нашли — возвращаем nil
}

// Проверяем работу
let numbers = [3, 7, 1, 9, 4, 6, 8]
if let index = linearSearch(in: numbers, target: 9) {
    print("Элемент 9 найден на индексе (index)")  // Вывод: Элемент 9 найден на индексе 3
} else {
    print("Элемент не найден")
}

Пример 2: Линейный поиск — поиск всех вхождений

// Иногда нужно найти ВСЕ позиции элемента
func findAllOccurrences(in array: [T], target: T) -> [Int] {
    var indices: [Int] = []  // Массив для хранения всех индексов
    
    for (index, element) in array.enumerated() {
        if element == target {
            indices.append(index)  // Добавляем каждый найденный индекс
        }
    }
    
    return indices  // Возвращаем массив индексов (может быть пустым)
}

let scores = [85, 92, 78, 92, 88, 92, 90]
let positions = findAllOccurrences(in: scores, target: 92)
print("Оценка 92 встречается на позициях: (positions)")  // [1, 3, 5]

Пример 3: Бинарный поиск — итеративная версия

// Классический бинарный поиск (итеративный)
// ВАЖНО: массив должен быть отсортирован!
func binarySearchIterative(in sortedArray: [T], target: T) -> Int? {
    var left = 0  // Левая граница поиска
    var right = sortedArray.count - 1  // Правая граница поиска
    
    while left <= right {
        let mid = left + (right - left) / 2  // Середина (без переполнения)
        let midValue = sortedArray[mid]
        
        if midValue == target {
            return mid  // Нашли!
        } else if midValue < target {
            left = mid + 1  // Искомое больше — ищем в правой половине
        } else {
            right = mid - 1  // Искомое меньше — ищем в левой половине
        }
    }
    
    return nil  // Элемент не найден
}

let sortedNumbers = [1, 3, 5, 7, 9, 11, 13, 15]
if let index = binarySearchIterative(in: sortedNumbers, target: 7) {
    print("Число 7 найдено на индексе (index)")  // Вывод: Число 7 найдено на индексе 3
}

Пример 4: Бинарный поиск — рекурсивная версия

// Рекурсивная версия бинарного поиска
// Элегантнее, но может вызвать переполнение стека на очень больших массивах
func binarySearchRecursive(in sortedArray: [T], target: T, left: Int, right: Int) -> Int? {
    // Базовый случай: границы сошлись — элемент не найден
    guard left <= right else {
        return nil
    }
    
    let mid = left + (right - left) / 2
    let midValue = sortedArray[mid]
    
    if midValue == target {
        return mid  // Нашли!
    } else if midValue < target {
        // Ищем в правой половине
        return binarySearchRecursive(in: sortedArray, target: target, left: mid + 1, right: right)
    } else {
        // Ищем в левой половине
        return binarySearchRecursive(in: sortedArray, target: target, left: left, right: mid - 1)
    }
}

// Удобная обёртка для вызова
func binarySearch(in sortedArray: [T], target: T) -> Int? {
    return binarySearchRecursive(in: sortedArray, target: target, left: 0, right: sortedArray.count - 1)
}

let letters = ["a", "b", "c", "d", "e", "f", "g"]
if let index = binarySearch(in: letters, target: "e") {
    print("Буква 'e' найдена на индексе (index)")  // Вывод: Буква 'e' найдена на индексе 4
}

Пример 5: Поиск по словарю (Dictionary)

// Словарь — идеальный инструмент для поиска по ключу
// Создаём базу данных студентов (ID -> Имя)
var students: [Int: String] = [
    101: "Анна",
    102: "Борис",
    103: "Виктория",
    104: "Глеб"
]

// Поиск по ID — мгновенный!
func findStudent(byID id: Int) -> String? {
    // Прямой доступ по ключу — O(1)
    return students[id]
}

// Проверяем
if let name = findStudent(byID: 103) {
    print("Студент с ID 103: (name)")  // Вывод: Студент с ID 103: Виктория
} else {
    print("Студент не найден")
}

// Поиск по имени (значению) — уже линейный поиск
func findStudent(byName name: String) -> Int? {
    // Приходится перебирать все пары ключ-значение
    for (id, studentName) in students {
        if studentName == name {
            return id
        }
    }
    return nil
}

if let id = findStudent(byName: "Борис") {
    print("Борис имеет ID: (id)")  // Вывод: Борис имеет ID: 102
}

Пример 6: Поиск с использованием замыканий (Closures)

// Современный Swift позволяет передавать условия поиска через замыкания
// Это делает код гибким и переиспользуемым

// Универсальная функция поиска с предикатом
func findFirst(in array: [T], where predicate: (T) -> Bool) -> T? {
    for element in array {
        if predicate(element) {
            return element  // Возвращаем первый подходящий элемент
        }
    }
    return nil
}

// Пример: ищем первое чётное число
let mixedNumbers = [1, 3, 7, 8, 9, 12, 15]
if let firstEven = findFirst(in: mixedNumbers, where: { $0 % 2 == 0 }) {
    print("Первое чётное число: (firstEven)")  // Вывод: Первое чётное число: 8
}

// Пример: ищем строку длиннее 5 символов
let words = ["кот", "собака", "дом", "автомобиль", "лес"]
if let longWord = findFirst(in: words, where: { $0.count > 5 }) {
    print("Первое длинное слово: (longWord)")  // Вывод: Первое длинное слово: собака
}

Пример 7: Комбинированный подход — поиск в структурах данных

// Реальная задача: поиск товаров в интернет-магазине
struct Product {
    let id: Int
    let name: String
    let price: Double
    let category: String
}

// Создаём каталог товаров
let catalog: [Product] = [
    Product(id: 1, name: "Ноутбук", price: 75000, category: "Электроника"),
    Product(id: 2, name: "Книга", price: 500, category: "Книги"),
    Product(id: 3, name: "Телефон", price: 45000, category: "Электроника"),
    Product(id: 4, name: "Футболка", price: 1500, category: "Одежда"),
    Product(id: 5, name: "Планшет", price: 30000, category: "Электроника")
]

// Функция поиска по категории с использованием filter
func findProducts(in category: String) -> [Product] {
    // filter — это встроенный линейный поиск с предикатом
    return catalog.filter { $0.category == category }
}

// Функция поиска по цене (бинарный поиск, если отсортировано)
func findProducts(under price: Double) -> [Product] {
    // Сортируем по цене для бинарного поиска
    let sortedByPrice = catalog.sorted { $0.price < $1.price }
    
    // Используем бинарный поиск для нахождения границы
    var result: [Product] = []
    for product in sortedByPrice {
        if product.price <= price {
            result.append(product)
        } else {
            break  // Так как массив отсортирован, дальше искать не нужно
        }
    }
    return result
}

// Демонстрация
let electronics = findProducts(in: "Электроника")
print("Товары категории 'Электроника':")
for product in electronics {
    print("- (product.name): (product.price) руб.")
}

let cheapProducts = findProducts(under: 2000)
print("
Товары дешевле 2000 руб.:")
for product in cheapProducts {
    print("- (product.name): (product.price) руб.")
}

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

🔑 Ключевое отличие: В Swift ты всегда знаешь, какой тип данных ищешь — компилятор проверит это за тебя. В Python ты можешь случайно сравнить число со строкой, и это вызовет ошибку только во время выполнения.

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

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

// ❌ НЕПРАВИЛЬНО
let unsorted = [5, 2, 8, 1, 9]
let index = binarySearchIterative(in: unsorted, target: 8)  // Может вернуть nil или неверный индекс!

// ✅ ПРАВИЛЬНО
let sorted = unsorted.sorted()  // [1, 2, 5, 8, 9]
let correctIndex = binarySearchIterative(in: sorted, target: 8)  // Вернёт 3

Ошибка 2: Путаница между индексом и значением

// ❌ НЕПРАВИЛЬНО
let array = [10, 20, 30, 40]
let target = 30
// Пытаемся сравнить индекс со значением
for i in 0..

// ❌ НЕПРАВИЛЬНО — принудительное извлечение
let numbers = [1, 2, 3]
let index = numbers.firstIndex(of: 5)!  // Crash! Элемента нет

// ✅ ПРАВИЛЬНО — безопасное извлечение
if let index = numbers.firstIndex(of: 5) {
    print("Нашли на индексе (index)")
} else {
    print("Элемент не найден")
}

// ❌ НЕПРАВИЛЬНО — бинарный поиск для неотсортированных данных
let data = [9, 3, 7, 1, 5]
// Сортируем только для поиска — теряем исходный порядок!
let sortedData = data.sorted()
let index = binarySearchIterative(in: sortedData, target: 7)
// Индекс будет 3, но в исходном массиве 7 была на индексе 2!

// ✅ ПРАВИЛЬНО — используем линейный поиск
if let originalIndex = data.firstIndex(of: 7) {
    print("В исходном массиве 7 на индексе (originalIndex)")  // 2
}

// ❌ НЕПРАВИЛЬНО — может вызвать переполнение на больших массивах
let mid = (left + right) / 2  // Если left + right > Int.max, будет ошибка

// ✅ ПРАВИЛЬНО — безопасное вычисление
let mid = left + (right - left) / 2  // Никогда не переполнится