Why would you ever do Binary Search on a Doubly-Linked list?

Technology CommunityCategory: Linked ListsWhy would you ever do Binary Search on a Doubly-Linked list?
VietMX Staff asked 1 year ago
Problem

As it already takes O(n) time to search a doubly-linked list for an element why would you do binary search on it?

One major advantage of this approach is that even though the runtime is O(n), we only end up doing O(log n) total comparisons (one per step of the binary search). This means that if comparisons are expensive, we might end up doing less work using a binary search than doing a normal linear search, since the O(n) comes from the work done walking the list rather than the work done making comparisons.