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

Бинарный поиск в отсортированном массиве работает за O(log n), потому что на каждом шаге исключает половину кандидатов. Линейный поиск в худшем случае просматривает n элементов.

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