answersLogoWhite

0

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.

User Avatar

Wiki User

14y ago

Still curious? Ask our experts.

Chat with our AI personalities

BeauBeau
You're doing better than you think!
Chat with Beau
MaxineMaxine
I respect you enough to keep it real.
Chat with Maxine
FranFran
I've made my fair share of mistakes, and if I can help you avoid a few, I'd sure like to try.
Chat with Fran
More answers

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.

User Avatar

Wiki User

11y ago
User Avatar

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.

User Avatar

Wiki User

14y ago
User Avatar

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.

User Avatar

Wiki User

9y ago
User Avatar

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.

User Avatar

Wiki User

8y ago
User Avatar

Add your answer:

Earn +20 pts
Q: Why can't we perform binary search in linked lists?
Write your answer...
Submit
Still have questions?
magnify glass
imp
Continue Learning about Engineering

What are the advantages and disadvantages of binary search algorithms?

the major limitation of binary search is that there is a need of sorted array to perform binary search operation. if array is not sorted the output is either not correct or may be after a long number of steps and according to data structure the output should come in minimum number of steps.


What advantages of a sorted list over a linked list?

All lists are linked lists; there is no such thing as a separate "sorted list". There are algorithms that can sort a list, of course, but they all work on linked lists.


How linked list used in car parking?

It isn't. In car parking the only thing we need to keep track of is tickets. When we issue a new ticket we place it at the end of the array. When we extract a (paid) ticket, we simply move the last ticket into its place. This allows constant-time insertion and extraction. The only cost is that we must perform a linear search in order to locate a ticket for extraction, but we can perform linear searches across an array much quicker than we can with a linked-list because we don't have the additional cost of dereferencing individual nodes. Note that even if the list were in sorted order, we cannot use a binary search because lists do not allow constant-time random access. Arrays do allow efficient binary searches but we must maintain sorted order to do so and that may well cost more than a simple linear search. Given that linear search must be performed regardless of which container we use, an array is the better choice of the two.


How do you compare items in a linked list?

You compare items in a linked list by searching for them. Iterate through the list, comparing elements with the search key. If you encounter end-of-list, then the key is not found, otherwise you have found the element desired. Note that this is a half linear search. Statistically, if an element is to be found, it will be found at the halfway point, assuming uniformly random distribution of data. In the worst case, if the element is not found, it will always take a full search to prove that. You could keep the linked list in order, by inserting each element before the element that has higher key value. This would reduce search time to half, because searching would stop with the element with higher key value. Searching is not a very efficient use of a linked-list. It would be better to use some kind of ordered list, perhaps a dynamic array with binary search, or a balanced binary tree, which has similar search performance but one with the most cost to design and implement. Linked-lists are better for keeping elements in the order they were encountered or inserted, such as processing tokens in a compiler. Sorry, but every solution has its tradeoffs.


5 Why Searching is slower in Linked-List than in Trees?

Searching is slower for linked-lists rather than (ordered) trees because you need to iterate through each element serially, whereas for an ordered (binary) tree you use a "divide and conquer", otherwise known as binary search, method. Think of it this way. Think of a number between 1 and 128. Perhaps the number is 97. With an ordered list, it would take 97 comparisons to find the item. With an unordered list, it would take an average of 64 comparisons - if the order was random. With a binary tree, i.e. a binary search, you only need 7 comparisons. In fact, you never need more than 7 comparisions for a tree size of 128, and on average, you would use less than that.