Introduction
In this article, we will learn how to perform a binary search on linked list in an effective way. Binary Search is a searching algorithm which is performed on the sorted elements in which element is searched in the middle portion of the linked list. We already know binary search will be used on sorted data. So let’s understand how can we perform a binary search on linked list.
Problem Statement
In this problem, we are given a sorted Singly Linked List and an integer X, and we need to find and tell if the list contains a given element X or not.
Problem Statement Understanding
Let’s learn programming languages online and try to understand the problem statement with the help of examples.
If the given linked list is
- According to the problem statement, the given linked list is sorted, and we need to tell if the list contains element X or not.
- If element X is present we will print Element Found else we print Element not Found.
- We can see that X = 5 is present in the linked list, so we will print ‘Element Found’.
If the given sorted linked list is head→1→3→5→7→9→NULL and X=8.
- So we can see that X = 8 is not present in the given linked list, so we will print Element not Found.
Now I think from the above examples, the problem is clear. So let’s see how we can approach it.
A straightforward way to check if an element X is present in the linked list is to traverse the linked list and check if for any node (node→data == X):
- If node→data == X, it will mean that element X is present in the linked list.
- Otherwise, if none of the node’s data is equal to X during the whole traversal, it will mean that element X is not present in the linked list.
Although the above linear traversal to check if any element X is present in the linked list or not will work fine, but here we are asked to use Binary search.
So let’s see how we can use binary search to check if an element X is present in a linked list or not.
Approach of binary search on linked list
Here we will see how we can use binary search algorithm to check whether a certain element X is present in the given list or not.
Initially, the range of binary search will be the complete list, i.e., from head to the last node of the list. Binary search first compares the target element X with the middle element based on which it reduces the range for further search.
- If the middle element is equal to the target element X, then we have found our element.
- Else, if the target element X is less than the middle element, then the range of binary search will reduce, and our new range will be from start to middle element of the linked list.
- Else, If the target element X is greater than the middle element, the search range will reduce and our new search range will be from middle→next to the end of the list.
The searching will go on until one of the following condition hits:
- We find element X.
- The search range collapses, and we don’t have any element in the search range to check.
The time complexity of binary search on linked list is O(log n) which is much better than linear search which takes linear time O(n) to search an element, but for binary to work properly the given must be sorted. Its time complexity is less than O(n) because it does not check every element of the given list. The search reduces to half at every iteration.
Let’s see the algorithm.
Algorithm to perform binary search in linked list
To find an element X in the singly linked list, we need to find the middle of the list and then divide the list into 2 halves and perform the operations on the favorable part of the list and repeat the above steps until we find the required key in the list.
- First, we need to find the middle node of the linked list, which we will find using the slow and fast pointer method.
- In slow and fast pointer method, we will run a while loop until the fast pointer or next of the fast pointer hits null and in each iteration, we will move fast by 2 nodes at a time (fast = fast→next→next) and slow one node at a time ( slow=slow→next).
- So when the pointers exit the while loop, the slow pointer will be pointing to the middle node of the linked list.
- Then, after finding the middle node of the list, we need to compare the value of the middle node of the list with the target element X.
- If the middle node value of the list is equal to target element X, so we return middle as the answer.
- If the middle node value is less than the target element X, we update the start pointer with middle→next.
- If the middle node value is greater than the element X, we update the last pointer to the middle node.
- We perform the above operations until the start node equals last node or the last node becomes NULL.
- Then we check if the node returned by the function is not NULL we print Element Found else we print Element not Found.
Dry Run
Code Implementation:
#include<stdio.h> #include<stdlib.h> struct Node { int data; struct Node* next; }; struct Node *newNode(int x) { struct Node* temp = (struct Node*)malloc(sizeof(struct Node)); temp->data = x; temp->next = NULL; return temp; } // function to find out middle element struct Node* middle(struct Node* start,struct Node* last) { if (start == NULL) return NULL; struct Node* slow = start; struct Node* fast = start -> next; while (fast != last) { fast = fast -> next; if (fast != last) { slow = slow -> next; fast = fast -> next; } } return slow; } // Function for implementing the Binary // Search on linked list struct Node* binarySearch(struct Node *head, int value) { struct Node* start = head; struct Node* last = NULL; do { // Find middle struct Node* mid = middle(start, last); // If middle is empty if (mid == NULL) return NULL; // If value is present at middle if (mid -> data == value) return mid; // If value is more than mid else if (mid -> data < value) start = mid -> next; // If the value is less than mid. else last = mid; } while (last == NULL || last != start); // value not present return NULL; } // Driver Code int main() { struct Node *head = newNode(1); head->next = newNode(4); head->next->next = newNode(7); head->next->next->next = newNode(8); head->next->next->next->next = newNode(9); head->next->next->next->next->next = newNode(10); int value = 8; if (binarySearch(head, value) == NULL) printf("Value not present\n"); else printf("Present"); return 0; }
#include<bits stdc++.h=""> using namespace std; struct Node { int data; struct Node* next; }; Node *newNode(int x) { struct Node* temp = new Node; temp->data = x; temp->next = NULL; return temp; } struct Node* find_middle_node(Node* start, Node* last) { if (start == NULL){ return NULL; } struct Node* slow = start; struct Node* fast = start -> next; while (fast != last) { fast = fast -> next; if (fast != last) { slow = slow -> next; fast = fast -> next; } } return slow; } struct Node* binarySearch(Node *head, int value){ struct Node* start = head; struct Node* last = NULL; do { Node* mid = find_middle_node(start, last); if (mid == NULL){ return NULL; } if (mid -> data == value){ return mid; } else if (mid -> data < value){ start = mid -> next; } else{ last = mid; } } while (last == NULL || last != start); return NULL; } int main() { Node *head = newNode(2); head->next = newNode(5); head->next->next = newNode(7); head->next->next->next = newNode(11); head->next->next->next->next = newNode(15); head->next->next->next->next->next = newNode(18); int value = 5; if (binarySearch(head, value) == NULL) printf("Element not Found\n"); else printf("Element Found"); return 0; }
class Node { int data; Node next; Node(int d) { data = d; next = null; } } class BinarySearch { static Node push(Node head, int data) { Node newNode = new Node(data); newNode.next = head; head = newNode; return head; } static Node middleNode(Node start, Node last) { if (start == null) return null; Node slow = start; Node fast = start.next; while (fast != last) { fast = fast.next; if (fast != last) { slow = slow.next; fast = fast.next; } } return slow; } static Node binarySearch(Node head, int value) { Node start = head; Node last = null; do { Node mid = middleNode(start, last); if (mid == null) return null; if (mid.data == value) return mid; else if (mid.data > value) { start = mid.next; } else last = mid; } while (last == null || last != start); return null; } public static void main(String[] args) { Node head = null; head = push(head, 2); head = push(head, 5); head = push(head, 7); head = push(head, 11); head = push(head, 15); head = push(head, 18); int value = 7; if (binarySearch(head, value) == null) { System.out.println("Element not found"); } else { System.out.println("Element found"); } } }
class Node: def __init__(self, data): self.data = data self.next = None self.prev = None def newNode(x): temp = Node(0) temp.data = x temp.next = None return temp def middle(start, last): if (start == None): return None slow = start fast = start . next while (fast != last): fast = fast . next if (fast != last): slow = slow . next fast = fast . next return slow def binarySearch(head,value): start = head last = None while True : mid = middle(start, last) if (mid == None): return None if (mid . data == value): return mid elif (mid . data < value): start = mid . next else: last = mid if not (last == None or last != start): break return None head = newNode(2) head.next = newNode(5) head.next.next = newNode(7) head.next.next.next = newNode(11) head.next.next.next.next = newNode(15) head.next.next.next.next.next = newNode(18) value = 9 if (binarySearch(head, value) == None): print("Element not Found\n") else: print("Element Found")
Output
Element Found
Time Complexity: O(n), where n is the total number of nodes in the Singly Linked List though we are performing a Binary search still in the worst case the complexity is O(n).
Conclusion
In this blog, we learned to perform a binary search on linked list. Our experts continuously try to give you a better choice of questions, you can follow the link and masters in the linked list. We hope you will understand how to apply binary search on linked list.
FAQs
- Can we do a binary search on linked list?
- Which search is best for the linked list?
- Linear search on unordered lists. Which takes O(N).
- Binary search is possible by using a skip list.
- Why is binary search faster than linear search?
Yes, binary search is possible on linked lists if the linked list is in an ordered format and we know the count of the nodes in the linked list.
You have two choices for applying search algorithms on linked lists:
Binary search is faster than linear search when the given array is already sorted.