Какая сложность поиска элементов в отсортированном массиве?

Question

Бинарный поиск в отсортированном массиве имеет сложность O(log n). Линейный поиск — O(n), но он не использует преимущества сортировки.

YeaHub · Accepted Answer

1. Бинарный поиск:Делит массив пополам на каждом шаге.Работает только с отсортированными данными.2. Пример на Swift:func binarySearch(_ array: [Int], _ target: Int) -> Int? {
    var low = 0
    var high = array.count - 1
    while low <= high {
        let mid = (low + high) / 2
        if array[mid] == target { return mid }
        else if array[mid] < target { low = mid + 1 }
        else { high = mid - 1 }
    }
    return nil
}Вывод:Для отсортированных данных всегда используйте бинарный поиск.