We use binary search because, in this, it is not required to iterate over every node. We only search for the target value in a possible range. To be more specific, we deploy a divide-and-conquer approach. Through this approach, the search space becomes half at each step until we find the target element or the search space is exhausted(element not present). Whereas in a linear search, we iterate over all the linked list nodes and compare the data with the target. If they are equal, the target is present, and we end the traversal. Otherwise, continue until we find the target or reach the end of the list.
There is one constraint to be able to perform binary search and that is the data structure on which the binary search is to be done must contain elements in sorted order.
You are given a sorted, singly linked list of integers and a target element. You need to find whether the target element is present in the linked list or not.
Example
Given a target value and a sorted linked list. Find whether the element is present in the linked list or not.
Input
Linked List: 10->12->15->16->20->NULL
Target = 16
Output
Target found
Explanation
For target=16 since 16 is there in the linked list, the output will be “Target found.”
Analysis of the problem statement
If we analyze the problem statement, we get that it says we need to search for a target value in the linked list. So if we use the traditional linear search technique, it will be very costly to us in terms of time. As we read above, we must iterate through every node in a linear search. So in this article, we will learn about a better approach to solving this problem. This approach will use the technique of binary search.
As in binary search, we need to know the middle element. There is a prerequisite to this problem, that is, to find the middle node of a linked list. So, please consider reading the article Finding the Middle Node of a Linked List, as after understanding this concept, the binary search algorithm will be a cakewalk.
Approach
Define two pointers - startand end. Start points to the head of the linked list, and endpoints to the last node of the linked list.
Find the middle node of the linked list using the approach of the fast and slow pointers. Let the mid pointer point it.
Compare the value of the middle node with the target element. There can be three cases-
If mid->value == target: then print “Target found” and break the loop.
If mid->value < target: then it implies that the target lies in the right half of the list as its value is greater than that of the middle node. So, we update the start pointer to point the node next to the middle node, i.e., start=mid->next.
If mid->value > target: then it means that the target lies in the left half of the linked list since its value is lesser than that of the middle node. So, we should search for it in the left half of the list. Thus, we should update the end pointer to point to the node just before the middle node. We have a mid pointer, but we can’t access the node just before it as we don’t have any previous pointer in our node structure. So, we simply update the end pointer as end = mid.
Repeat the above steps until the search space is exhausted. That is, until the start becomes equal to the end(both pointers pointing to the same node) or the end becomes NULL.
Dry Run
Let’s say we are given a Linked list sorted in ascending order and target/key element.
Start-> value=10 End->value=25. Find Middle node-
Since mid->value = 15 and target = 16, so target>mid->value. Update Start as Start=mid->next and continue to find the middle node again.
Start->value=15 and End->value=25. Let’s find the middle Node-
Since mid->value = 20 and target =16, so target<mid->value. Update End as End=mid and continue to find the middle node again.
Start->value=16 and End->value=20. Let’s find the middle Node-
Here, mid->value=16 and target = 16. Since target=mid->value, we have found the target element in the linked list. So, print “Target element found,” and the process is terminated.
Let’s see the code implementation and the analysis of time and space complexity in the next section.
C++ Implementation
// CPP code to implement binary search
// on Singly Linked List
#include<bits/stdc++.h>
using namespace std;
// structure of a node of the linked list
struct Node
{
int data;
struct Node* next;
};
// Creating Node
Node *newNode(int x)
{
struct Node* temp = new Node;
temp->data = x;
temp->next = NULL;
return temp;
}
// function to find the middle node of the linked list
struct Node* middle(Node* start, Node* last)
{
// if list is empty
if (start == NULL) return NULL;
// defining two pointers: slow and fast
struct Node *slow = start;
struct Node *fast = start;
while(fast->next != last && fast->next->next != last){
fast = fast->next->next;
slow = slow->next;
}
// slow points to the mid of the linked list
return slow;
}
// Implementing the Binary Search
struct Node* binarySearch(Node *listHead, int target)
{
struct Node* start = listHead;
struct Node* last = NULL;
while(last != start) {
// Find middle
Node* mid = middle(start, last);
// If middle is empty
if (mid == NULL) return NULL;
// If target is present at middle
if (mid -> data == target) return mid;
// If target is more than mid
else if (mid -> data < target) start = mid -> next;
// If the target is less than mid.
else last = mid;
}
// target not present
return NULL;
}
int main()
{
Node *listHead = newNode(10);
listHead->next = newNode(12);
listHead->next->next = newNode(15);
listHead->next->next->next = newNode(16);
listHead->next->next->next->next = newNode(20);
listHead->next->next->next->next->next = newNode(25);
int target = 16;
if (binarySearch(listHead, target) == NULL)
cout << "Target element:" << target << " not present in the linked list\n";
else
cout << "Target element:" << target << " present in the linked list\n";
return 0;
}
You can also try this code with Online C++ Compiler
import java.util.*;
// structure of a node of the linked list
class Node {
int data;
Node next;
Node(int data) {
this.data = data;
this.next = null;
}
}
public class Main {
// function to create a new node
public static Node newNode(int x) {
Node temp = new Node(x);
return temp;
}
// function to find the middle node of the linked list
public static Node middle(Node start, Node last) {
// if list is empty
if (start == null) return null;
// defining two pointers: slow and fast
Node slow = start;
Node fast = start;
while (fast.next != last && fast.next.next != last) {
fast = fast.next.next;
slow = slow.next;
}
// slow points to the mid of the linked list
return slow;
}
// Implementing the Binary Search
public static Node binarySearch(Node listHead, int target) {
Node start = listHead;
Node last = null;
while (last != start) {
// Find middle
Node mid = middle(start, last);
// If middle is empty
if (mid == null) return null;
// If target is present at middle
if (mid.data == target) return mid;
// If target is more than mid
else if (mid.data < target) start = mid.next;
// If the target is less than mid.
else last = mid;
}
// target not present
return null;
}
public static void main(String[] args) {
Node listHead = newNode(10);
listHead.next = newNode(12);
listHead.next.next = newNode(15);
listHead.next.next.next = newNode(16);
listHead.next.next.next.next = newNode(20);
listHead.next.next.next.next.next = newNode(25);
int target = 16;
if (binarySearch(listHead, target) == null)
System.out.println("Target element: " + target + " not present in the linked list");
else
System.out.println("Target element: " + target + " present in the linked list");
}
}
You can also try this code with Online Java Compiler
# Python code to implement binary search on Singly Linked List
# structure of a node of the linked list
class Node:
def __init__(self, data=None, next=None):
self.data = data
self.next = next
# function to create a new node
def new_node(x):
temp = Node(x)
return temp
# function to find the middle node of the linked list
def middle(start, last):
# if list is empty
if start is None:
return None
# defining two pointers: slow and fast
slow = start
fast = start
while fast.next != last and fast.next.next != last:
fast = fast.next.next
slow = slow.next
# slow points to the mid of the linked list
return slow
# Implementing the Binary Search
def binary_search(list_head, target):
start = list_head
last = None
while last != start:
# Find middle
mid = middle(start, last)
# If middle is empty
if mid is None:
return None
# If target is present at middle
if mid.data == target:
return mid
# If target is more than mid
elif mid.data < target:
start = mid.next
# If the target is less than mid.
else:
last = mid
# target not present
return None
list_head = new_node(10)
list_head.next = new_node(12)
list_head.next.next = new_node(15)
list_head.next.next.next = new_node(16)
list_head.next.next.next.next = new_node(20)
list_head.next.next.next.next.next = new_node(25)
target = 16
result = binary_search(list_head, target)
if result is None:
print("Target element:", target, "not present in the linked list")
else:
print("Target element:", target, "present in the linked list")
You can also try this code with Online Python Compiler
The time complexity of the above-stated code is O(n), where n is the number of elements in the linked list. Since it takes time proportional to n/2 to find the middle node in a linked list. So, the recurrence relation for the binary search on the linked list becomes -
T(n) = T(n/2) + O(n).
According to Case-3 of the Master’s Theorem for analysis of algorithms, the time complexity will be O(n).
Space Complexity
The space complexity is O(1), as no extra space is used in this algorithm.
Frequently Asked Questions
What are linked lists?
A linked list is a data structure consisting of a sequence of elements, each containing a reference to the next element in the sequence. The elements are called nodes, and the reference is called a pointer.
What is binary search?
Binary search is an algorithm for efficiently finding an item in a sorted list by repeatedly dividing the search interval in half and checking the middle element.
What is the time complexity of performing a binary search on linked lists?
The time complexity of performing a binary search on a linked list is O(n).
What is the space complexity of performing a binary search on linked lists?
The space complexity of performing a binary search on linked lists is O(1).
Why is a binary search on arrays better than linked lists?
Binary search on arrays is better than binary search on linked lists because on arrays, the time complexity is O(logn), and in linked lists, it is O(n). This is because, in a linked list, elements are not stored in contiguous memory locations.
Conclusion
In this article, we learned the application of binary search on linked lists. We learned about the intuition and approach for this algorithm. We also learned about its implementation in popular programming languages and their complexity analysis.
Check out our articles if you think this blog has helped you enhance your knowledge and want to learn more. Visit our website to read more such blogs.
8+ registered 