CODEWITHSUNDEEP
data-structures
Faysal Hasan
Faysal Hasan

Reputation: 119

Why binary search is not possible in sorted linked list?

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"?

Upvotes: 4

Views: 14774

Answers (3)

thang
thang

Reputation: 3466

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

Upvotes: 11

dfeuer
dfeuer

Reputation: 48611

ethang shows how to perform binary search in a singly linked list with just O(1) extra space, O(n) traversal time, and O(log n) comparisons. I did not previously believe that this was possible. For fun, I figured I'd implement a similar algorithm in Haskell:

bs :: Ord k => Int -> k -> [(k,v)] -> Maybe v
bs 0 _ _ = Nothing
bs 1 needle ((k,v) : _)
  | k == needle = Just v
  | otherwise = Nothing
bs size needle left = case drop size' left of
    right@((k,_):_)
      | needle >= k -> bs (size - size') needle right
    _ -> bs size' needle left
  where size' = size `quot` 2

search :: Ord k => k -> [(k,v)] -> Maybe v
search k kvs = bs (length kvs) k kvs

This can be adjusted to use O(log i) comparisons and O(i) traversal time, where i is the distance from the beginning of the list to the location where the sought key is or would be. This implementation could be improved, but the gist is quite simple—replace the search above with this version:

import Control.Applicative ((<|>))

search :: Ord k => k -> [(k,v)] -> Maybe v
-- The 10 can be replaced by any positive integer
search = go 10
  where
    -- The 2 can be replaced by any integer > 1
    go lim needle kvs@((k,_):_) | k <= needle =
      bs lim needle kvs <|> go (lim*2) needle (drop lim kvs)
    go _ _ _ = Nothing

Upvotes: 1

user4098326
user4098326

Reputation: 1742

A linked list only allows sequential access, so binary search is impossible even if the list is sorted.

Edit: As others have pointed out, binary search is possible, but would be pointless.

We can emulate random access in a linked list, but that would be slow and has a time complexity of O(n) on average, so a binary search(which is normally O(lgn)) will take O(nlgn).

Edit 2: as @ethang pointed out, if it's a doubly linked list, the binary search can take only O(n). In each step, we can start from the previous position instead of from the head/tail, so the distance moved will half each time.

If you must use a linked list, you'd better using a linear search, whose complexity is only O(n), and is simpler than a binary search.

If you want to both search and insert/remove effectively, you may use other data strictures such as a binary search tree.

Upvotes: 2

Related Questions