Qual è la complessità asintotica dell'algoritmo di ricerca binaria quando viene utilizzato per cercare in liste collegate?

Асимптотическая сложность бинарного поиска в массиве — O(log n), так как доступ к элементу по индексу происходит за O(1).

Однако при использовании бинарного поиска в связном списке ситуация меняется, потому что для доступа к среднему элементу нужно пройти половину списка, что занимает O(n) времени.

Таким образом, каждый шаг бинарного поиска требует O(n) для доступа к элементу, а всего таких шагов O(log n). Итоговая асимптотика — O(n log n).

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