Algorithms and Data Structures · Senior · Question 42 of 75
Why can't you run binary search efficiently on a linked list?
- 1Linked lists can't be kept in sorted order
- ✓Correct answer: Reaching the middle takes O(n), so there's no random access
- 3Binary search needs the length, and lists have none
Explanation
Binary search relies on O(1) access by index. On a list each halving step walks half the remaining nodes, so the total is O(n). Skip lists add extra pointers to restore O(log n).