How to apply Binary Search O(log n) on a sorted Linked List?

Technology CommunityCategory: Linked ListsHow to apply Binary Search O(log n) on a sorted Linked List?
VietMX Staff asked 3 years ago
Problem

Sorted singly linked list is given and we have to search one element from this list. Time complexity should not be more than O(log n). How would you apply binary search on a sorted linked list?

It is certainly not possible with a plain singly-linked list. As linked list does not provide random access if we try to apply binary search algorithm it will reach O(n) as we need to find length of the list and go to the middle. To avoid this problem you need to use skip list.