Какая сложность поиска по массиву в Swift?

Массив в Swift — это упорядоченная коллекция элементов. Поиск по массиву включает перебор каждого элемента до нахождения совпадения.

Пример линейного поиска:

let numbers = [1, 3, 5, 7, 9]
if let index = numbers.firstIndex(of: 5) {
    	print("Index of 5: \(index)") // 2
} else {
    	print("Not found")
}

Здесь сложность равна O(n), так как в худшем случае придется проверить каждый элемент массива.

Оптимизация с помощью сортировки:

Если массив отсортирован, можно использовать бинарный поиск для повышения эффективности:

let sortedNumbers = [1, 3, 5, 7, 9]
let target = 5
let index = sortedNumbers.binarySearch(for: target) // Требуется реализация

Бинарный поиск снижает сложность до O(log n), но это возможно только для отсортированных массивов.

Для частых поисковых операций рекомендуется использовать другие коллекции, такие как словари (Dictionary) или множества (Set), которые предоставляют поиск за O(1).