Find the middle of unknown size list

Question

In a recent interview I was asked:

Find the middle element of a sorted List of unknown length starting from the first position.

I responded with this:

Have 2 position counters:

counter1 counter2

Increment counter1 by 1 and counter2 by 2. When counter 2 reaches the end of the list counter 1 will be in the middle. I feel that this isn't efficient because I am revisiting nodes I have already seen. Either way, is there a more efficient algorithm?

Answer 1

Assuming a linked list, you can do it while visiting arbitrarily-close-to N of the items.

To do 5/4 N:

• Iterate over the list until you hit the end, counting the items.
• Drop an anchor at every power of 2'th element. Track the last 2 anchors.
• Iterate the before-last anchor until it reaches the middle of the list.

When you hit the end of the list, the before-last anchor is before the mid-point but at least half way there already. So N for the full iteration + at most 1/4 N for the anchor = 5/4 N.

Dropping anchors more frequently, such as at every ceiling power of 1.5^th item, gets you as close to N as needed (at the cost of tracking more anchors; but for any given X as the power step, the asymptotic memory is constant).

Answer 2

I assume you're discussing a linked-list. Indeed your solution is an excellent one. An alternative would be to simply traverse the list counting the number of elements, and then start over from the beginning, traversing half the counted amount. Both methods end up traversing 3n/2 nodes, so there isn't much difference.

It's possible there may be slight cache advantages to either method depending on the architecture; the first method might have the advantage of having cached nodes which could mean quicker retrieval if the cache is large enough before the two pointers are two far apart. Alternatively, the cache might get better blocks if we traverse the list in one go, rather than keeping two pointers alive.

Answer 3

Presuming you can detect that you're beyond the end of the list and seek an arbitrary position efficiently within the list, you could keep doubling the presumed length of the list (guess the length is 1, then 2, then 4, ...) until you're past the end of the list, then use a binary search between the last attempted value less than the length of the list and the first value that exceeded the end of the list to find the actual end of the list.

Then, seek the position END_OF_LIST / 2.

That way, you do not have to visit every node.