В отсортированном массиве бинарный поиск занимает O(log n), а в односвязном списке обычный поиск — O(n) в худшем случае. Быстрый доступ к середине у списка отсутствует.
Где поиск быстрее: в отсортированном массиве или списке?
В отсортированном массиве бинарный поиск занимает O(log n), а в односвязном списке обычный поиск — O(n) в худшем случае. Быстрый доступ к середине у списка отсутствует.
Короткий ответ
Что ответить на собеседовании
Подробный разбор
Ответ с пояснениями
Условие
Нужно найти число 2 в двух структурах из n упорядоченных целых: массиве с доступом по индексу за O(1) и односвязном списке. Повторения допустимы; достаточно определить наличие. Сравните асимптотику и объясните влияние расположения числа.
Ответ
В отсортированном массиве бинарный поиск занимает O(log n), а в односвязном списке обычный поиск — O(n) в худшем случае. Быстрый доступ к середине у списка отсутствует.
Двоичный поиск сокращает диапазон, используя индекс середины; в списке до него приходится проходить узлы. Конкретное число 2 может оказаться в первом узле и найтись за O(1), поэтому нельзя обещать преимущество массива на каждом входе. Асимптотика описывает рост числа операций для класса задач. При сравнении реального времени также учитывают кеш-локальность, размер данных и стоимость построения структуры.