Why can't we perform binary search in linked lists?

Answer 1

The binary search algorithm depends on equal (or direct) access time for any selected element of a list. A linked list, however, does not provide that, so a binary search is inappropriate for a linked list.

Answer 2

Yes. Although a linked list is generally thought to mean a singly-linked list or a doubly-linked list, a binary search tree is really just another type of linked list. In fact it is a slightly modified doubly-linked list. In a doubly-linked list, each node has two pointers, one to the previous node, the other to the next node. In a binary tree, each node also has two pointers, one to the left node and one to the right node. The left node is effectively the root node of another binary tree containing values that are all less than this node's value, while the right node is the root node of another binary tree containing values greater than or equal to this node.

The first value inserted into the tree automatically becomes the root node. Thereafter, you pass new values to the root node. If the current value is less than the current node's value, pass it on to the left node, otherwise pass it on to the right node and recurse. If there is no node in the appropriate direction (the pointer is NULL), create a new node for the value and set the pointer.

Searching for values is essentially the same process; pass the value to the root. If the value is equal to the current node's value, return the node. If the value is less than the current node's value, pass the value to the left node, otherwise pass it to the right and recurse. If there is no node in that position, the value does not exist.

In order to optimise search times, it's better to use a balanced tree. This means there are the same number of nodes to the left of each node as there are to the right (plus/minus 1 node). All leaf nodes (those with neither left or right nodes) will therefore reside on no more than two levels at the bottom of the tree. Typically you will use a red/black tree for this. A red/black tree is a modified binary search tree that updates the links between the nodes upon each insertion in order to maintain balance. But you can achieve the exact same thing using a sorted array: simply start your search in the middle of the array and if the value is not there, you know it must either be in the subarray to the left (if the value is smaller than the middle element's value) or to right. Either way, you eliminate half the array. Recurse with the remaining subarray. If the subarray is empty, the value does not exist.

Answer 3

Think. In what order are items placed in a linked list?

Does a binary search require items to be in sort order?

When you know the answer to these two questions all will be revealed.

Answer 4

There's nothing to stop us from performing binary search upon a linked list, but it would be highly inefficient to do so because linked lists do not support constant-time random-access. We can gain constant-time random-access by creating an array of node pointers, but given this requires a complete traversal of the list in order to create the array, it would be quicker to simply traverse the list until we find the value. However, if we plan on doing a lot of searches upon the same list, it would be worthwhile creating such an array as this need only been done once.

Answer 5

It's not that we cannot implement a binary search on a list, we can do that very easily. The problem is that it is not efficient to do so because lists do not support constant-time random-access.

To perform a binary search upon a container, we need to compare the value we seek with the value of the middle element. If that is not the value we seek, we exclude the appropriate half of the container (including the middle element) and repeat with the remaining half. We continue in this manner until the value is found or the remaining half of the container is empty, in which case the value does not exist.

Note that the container must be in sorted order to determine which half of the container to exclude upon each iteration of the algorithm.

Performing a binary search upon a sorted array is efficient because we have constant-time random-access. The algorithm can be defined recursively as follows (in pseudocode):

Algorithm bin_search (array[], begin, end, value) is:

IF end<begin THEN RETURN null

middle := start + (end - start) / 2

IF array[middle]=value THEN RETURN middle

IF array[middle]<value THEN

RETURN bin_search (array, middle+1, end, value)

ELSE

RETURN bin_search (array, begin, middle, value)

An iterative approach is more efficient:

Algorithm bin_search (array, begin, end, value) is:

WHILE begin<end {

middle := start + (end - start) / 2

IF array[middle]=value THEN return middle

IF array[middle]<value THEN

begin := middle + 1

ELSE

end := middle

}

RETURN null

The problem with a list is that we don't have constant-time random-access, we only have constant-time access to the first and/or last elements. This means we must perform a linear search in order to locate the middle element which takes O(n/2) time for a list of n elements as opposed to the O(1) time for an array. Also, the iterators that define the half-closed range [begin:end) need to be bi-directional iterators, otherwise we incur even more inefficiency each time we have to establish a new upper bound within the lower half of the current range.

One way to improve efficiency is to create an array of iterators from the list and perform the binary search upon the array. This then gives us constant time access to the middle element, the only difference is that we must dereference that element in order to determine the value it refers to in the list. There's also the additional cost of constructing the array (which also consumes additional memory), however that only needs to be done once and only requires a single pass over the list. However, if the list changes in any way, the array is invalidated and must be reconstructed from scratch unless you provide some mechanism to keep both in sync.