algorithm - How is it possible to do binary search on a singly-linked list in O(n) time?

Question

This earlier question talks about doing binary search over a doubly-linked list in O(n) time. The algorithm in that answer work as follows:

• Go to the middle of the list to do the first comparison.
• If it's equal to the element we're looking for, we're done.
• If it's bigger than the element we're looking for, walk backwards halfway to the start and repeat.
• If it's smaller than the element we're looking for, walk forwards halfway to the start and repeat.

This works perfectly well for a doubly-linked list because it's possible to move both forwards and backwards, but this algorithm wouldn't work in a singly-linked list.

Is it possible to make binary search work in time O(n) on a singly-linked list rather than a doubly-linked list?

Answer 1

It's absolutely possible to make this work. In fact, there's pretty much only one change you need to make to the doubly-linked list algorithm to make it work.

The issue with the singly-linked list case is that if you have a pointer to the middle of the list, you can't go backwards to get back to the first quarter of the list. However, if you think about it, you don't need to start from the middle to do this. Instead, you can start at the front of the list and walk to the first quarter. This takes (essentially) the same amount of time as before: rather than going backward n / 4 steps, you can start at the front and go forwards n / 4 steps.

Now suppose you've done the first step and are at position n / 4 or 3n / 4. In this case, you're going to have the same problem as before if you need to back up to position n / 8 or position 5n / 8. In the case that you need to get to position n / 8, you can start at the front of the list again and walk forward n / 8 steps. What about the 5n / 8 case? Here's the trick - if you still have pointer to the n / 2 point, then you can start there and walk forwards n / 8 steps, which will take you to the right spot.

More generally, instead of storing a pointer to the middle of the list, store two pointers into the list: one at the front of the range where the value might be and one in the middle of the range where the value might be. If you need to advance forward in the list, update the pointer to the start of the range to be the pointer to the middle of the range, then walk the pointer to the middle of the range forward halfway to the end of the range. If you need to advance backward in the list, update the pointer to the middle of the range to be the pointer to the front of the range, then walk forwards halfway.

Overall, this has the exact same time complexity as the doubly-linked case: we take n / 2 steps, then n / 4 steps, then n / 8 steps, etc., which sums up to O(n) total steps. We also only make O(log n) total comparisons. The only difference is the extra pointer we need to keep track of.

Hope this helps!