Какова сложность кругового двусвязного списка с использованием бинарного поиска?

Question

Это O (n log n) или O (log n)?

Answer 1

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

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

Вы должны просто выполнить O (n) линейный поиск.

Answer 2

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