Why binary search is not possible in sorted linked list?

Question

Is it possible to search a element with binary search in sorted linked list? If it is not possible then the question is "why it is not possible"?

Answer 1

Binary search on a sorted array gives us the result in O(log N) comparisons and O(1) memory utilization. Linear search on a sorted array gives us the result in O(N) comparisons and O(1) memory utilization.

Beyond the normal memory and comparison measurements, we also have the idea of traversal steps. This is important for data structures with no random access. For example, in a linked list, to get to element j from the head, we would need to take j steps forward. These steps can happen without any comparison. As pointed out in the comments, the cost for making a traversal step may be different from the cost for making a comparison. A traversal step here translates to a memory read.

The question is what happens when our data structure is a sorted singly linked list? Is it worth doing binary search?

To address this, we need to look at the performance of binary search on a sorted singly linked list. The code looks like this:

struct Node {
        Node* next;
        int value;
};

Node* binarySearch(Node* n, int v) {
        if (v <= n->value) return n;

        Node *right, *left=n;
        int size = count(n);

        while (size > 1)
        {
                int newSize = (size / 2);

                right = left;
                for (int i = 0; (i < newSize) && (right->next!=nullptr); i++)
                        right = right->next;

                if (v == right->value) return right;
                else if (v > right->value) left = right;

                size -= newSize;
        }

        if (right && (v < right->value)) return right;
        else if (right->next) return right->next;
        else return nullptr;
}

The function binarySearch returns the node with element equal to or just greater than v. The parameter n is the head node in a sorted singly linked list.

It is clear that the outer loop iterates O(log N) times where N = size of the list. For each iteration, we make 2 comparisons, so the total # of comparisons is O(log N).

The number of traversal steps is the number of times right = right->next; gets executed, which is O(N). This is because the # of iterations in the inner loop decreases by half at each iteration of the outer loop, so N/2 + N/4 + ... + 1 = N (plus or minus some wiggle room).

Memory usage is still O(1).

In contrast, linear search through a sorted singly linked list is O(n) traversal steps, O(n) comparisons, and O(1) memory.

So is it worth doing binary search on a singly linked list? The answer is almost always yes, but not quite.

Disregarding the cost to count, what happens if the element we are looking for is the 2nd element in the list? Linear search takes 1 step and 1 comparison. Binary search takes ~ N steps and ~log N comparisons. Reality isn't so clear.

So here's the summary:

Sorted Array

 Binary: O(log N) comparisons, O(1) memory, O(log N) traversal steps
 Linear: O(N) comparisons, O(1) memory, O(N) traversal steps

Although, technically, the # of required traversal steps is 0 for sorted arrays. We never have to step forward or backwards. The idea doesn't even make sense.

Sorted Singly Linked List

 Binary: O(log N) comparisons, O(1) memory, O(N) traversal steps
 Linear: O(N) comparisons, O(1) memory, O(N) traversal steps

And these are worst case run time. However, the glass may not always be half empty :p