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.