Binary search cannot be performed on a linked list examine
Answers
Yes, Binary search is possible on the linked list if the list is ordered and you know the count of elements in list. But While sorting the list, you can access a single element at a time through a pointer to that node i.e. either a previous node or next node. This increases the traversal steps per element in linked list just to find the middle element. This makes it slow and inefficient.
Whereas the binary search on an array is fast and efficient because of its ability to access any element in the array in constant time. You can get to the middle of the array just by saying "array[middle]"! Now, can you do the same with a linked list? The answer is No. You will have to write your own, possibly inefficient algorithm to get the value of the middle node of a linked list. In a linked list, you loosse the ability to get the value of any node in a constant time.
One solution: to the inefficiency of getting the middle of the linked list during a binary search is to have the first node contain one additional pointer that points to the node in the middle. Decide at the first node if you need to check the first or the second half of the linked list. Continue doing that with each half-list.
Try to implement the algorithm and calculate the complexities.
I hope this will help you!