**Problem**

As it already takes

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

One major advantage of this approach is that even though the runtime is

, we only end up doing *O*(*n*)

total *O*(*log n*)**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

comes from the work done walking the list rather than the work done making comparisons.*O*(*n*)