Приведи пример эффективного алгоритма поиска и объясни его принцип.

Бинарный поиск (Binary Search) — классический эффективный алгоритм поиска элемента в отсортированном массиве.

Принцип работы ("разделяй и властвуй"):

1. Сравниваем искомый элемент (key) со средним элементом массива.
2. Если они равны — поиск завершен.
3. Если key меньше среднего элемента — повторяем поиск в левой половине массива.
4. Если key больше — повторяем поиск в правой половине.
5. Процесс повторяется, пока подмассив для поиска не станет пустым.

Реализация на Swift (итеративный подход):

func binarySearch<T: Comparable>(_ array: [T], key: T) -> Int? {
    var low = 0
    var high = array.count - 1

    while low <= high {
        let mid = (low + high) / 2 // Индекс среднего элемента
        if array[mid] == key {
            return mid // Элемент найден
        } else if array[mid] < key {
            low = mid + 1 // Ищем в правой половине
        } else {
            high = mid - 1 // Ищем в левой половине
        }
    }
    return nil // Элемент не найден
}

// Пример использования
let sortedNumbers = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
if let index = binarySearch(sortedNumbers, key: 23) {
    print("Элемент найден на индексе: (index)") // Напечатает: 5
}

Ключевые характеристики:

• Сложность: O(log n), что намного быстрее линейного поиска O(n) для больших массивов.
• Предварительное условие: Массив должен быть отсортирован.
• Применение: Используется в реализациях множеств (Set), словарей (Dictionary), при поиске в больших отсортированных наборах данных.