Какой алгоритм обеспечивает минимальную временную сложность поиска в отсортированном массиве?

Бинарный поиск (Binary Search) обеспечивает минимальную теоретическую сложность O(log n) для поиска в отсортированном массиве.

Принцип работы: Алгоритм делит отсортированный массив пополам, сравнивает искомый элемент с центральным и отбрасывает половину, в которой элемент заведомо отсутствует. Процесс повторяется для оставшейся половины.

Пример реализации на Swift:

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

    while lowerBound < upperBound {
        let midIndex = lowerBound + (upperBound - lowerBound) / 2

        if array[midIndex] == key {
            return midIndex
        } else if array[midIndex] < key {
            lowerBound = midIndex + 1
        } else {
            upperBound = midIndex
        }
    }
    return nil
}

Ключевые моменты:

• Требование: Массив должен быть отсортирован.
• Сложность: O(log n) по времени, O(1) по дополнительной памяти (в итеративной реализации).
• Альтернативы: Для маленьких массивов линейный поиск (O(n)) может быть проще. Для частых поисков по одному массиву эффективнее предварительно построить хеш-таблицу (O(1) в среднем).