Алгоритми та структури даних · Senior · Запитання 42 з 75
Чому бінарний пошук неефективний на зв'язному списку?
- 1Зв'язні списки не можна тримати відсортованими
- ✓Правильна відповідь: Дістатися середини коштує O(n), бо довільного доступу немає
- 3Бінарному пошуку потрібна довжина, а в списків її немає
Пояснення
Бінарний пошук спирається на доступ за індексом за O(1). У списку кожен крок ділення навпіл проходить половину вузлів, що лишилися, тож разом O(n). Skip list додає вказівники, щоб повернути O(log n).