Linked lists are not suitable for implementing Binary search

Linked List

A linked list is a data structure that consists of a sequence of nodes. Each node has two parts, i.e., data and a pointer that points to the next node in the sequence. The first node of the list is called the head, and the last node is called the tail. The tail node points to null, indicating the end of the list.

Binary Search

Binary search is an algorithm used to search for an element in a sorted array. The idea behind binary search is to repeatedly divide the search interval in half until the target element is found. If the target element is smaller than the middle element, then the search is continued in the left subarray; otherwise, it is continued in the right subarray.

Why Linked Lists are not suitable for implementing Binary Search?

1. Random Access

Binary search requires random access to the elements in the array. This means that we should be able to access any element in the array in constant time. However, in a linked list, we can only access the elements in a sequential manner. This means that we have to traverse the list from the beginning to reach the middle element, which takes linear time. Therefore, linked lists are not suitable for implementing binary search.

2. Time Complexity

The time complexity of binary search is O(log n), where n is the number of elements in the array. However, the time complexity of searching an element in a linked list is O(n). This is because we have to traverse the list from the beginning to find the target element. Therefore, linked lists are not efficient for implementing binary search.

Conclusion

Linked lists are not suitable for implementing binary search because they do not support random access to the elements, and the time complexity of searching an element is linear. Binary search requires constant time access to the elements and logarithmic time complexity, which is not possible with linked lists.