Вопрос относительно Руководства по разработке алгоритма - Структура данных для словаря

Question

Я начал читать Руководство по разработке алгоритмов, и, читая его, я наткнулся на одну строку, которую я не получаю. Может кто-нибудь уточнить, что автор имеет в виду здесь? Строка:

Сортированные связанные списки или массивы. Поддержание отсортированного связанного списка обычно не стоит усилий, если вы не пытаетесь устранить дубликаты, так как мы не может выполнить бинарный поиск в такой структуре данных. Отсортированный массив будет подойдет, если и только если не много вставок или удалений.

Эта строка в контексте выбора структуры данных для словаря. Я не понимаю, почему автор говорит, что «поддержание отсортированного связанного списка обычно не стоит усилий, если только вы не пытаетесь устранить дубликаты, , так как мы невозможно выполнить бинарный поиск в такой структуре данных"

Из того, что я понял, я погуглил, чтобы посмотреть, сможем ли мы выполнить бинарный поиск по отсортированным массивам и на основании того, что я нашел, похоже, мы можем. Так что я не уверен.

Может кто-нибудь помочь мне понять это?

Большое спасибо.

Answer 1

Вы не можете эффективно выполнять бинарный поиск по связанному списку, потому что вы не можете случайным образом искать его в постоянном времени.Чтобы найти середину, вы должны сделать n / 2 шага (пройти по списку).Это увеличивает накладные расходы и делает списки неподходящими для структур данных двоичного поиска.