Given a singly linked list and a key, the task is to find the key in the Linked List using Binary Search.
Examples:
Input: LinkedList = 1->4->7->8->9->10, key = 7
Output: Present
Input: LinkedList = 1->4->7->8->9->10, key = 12
Output: Value Not Present
Approach: To solve the problem using Binary search follow the below idea:
To perform a Binary search on a Linked List, the most important idea is to find the middle element of the Linked List on every iteration, which takes O(N) time everytime. This can be avoided if skip list is used.
- Find the middle element of the Linked List
- Compare the middle element with the key.
- If the key is found at the middle element, the process is terminated.
- If the key is not found at middle element, choose which half will be used as the next search space.
- If the key is smaller than the middle node, then the left side is used for the next search.
- If the key is larger than the middle node, then the right side is used for the next search.
- This process is continued until the key is found or the total Linked List is exhausted.
Below is the implementation of the above approach:
C++
// CPP code to implement binary search
// on Singly Linked List
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node* next;
};
Node* newNode(int x)
{
struct Node* temp = new Node;
temp->data = x;
temp->next = NULL;
return temp;
}
// function to find out middle element
struct Node* middle(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;
}
// Function for implementing the Binary
// Search on linked list
struct Node* binarySearch(Node* head, int value)
{
struct Node* start = head;
struct Node* last = NULL;
do {
// Find middle
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()
{
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 = 7;
if (binarySearch(head, value) == NULL)
printf("Value not present\n");
else
printf("Present");
return 0;
}
Java
// Java code to implement binary search
// on Singly Linked List
// Node Class
class Node
{
int data;
Node next;
// Constructor to create a new node
Node(int d)
{
data = d;
next = null;
}
}
class BinarySearch
{
// function to insert a node at the beginning
// of the Singly Linked List
static Node push(Node head, int data)
{
Node newNode = new Node(data);
newNode.next = head;
head = newNode;
return head;
}
// Function to find middle element
// using Fast and Slow pointers
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;
}
// function to insert a node at the beginning
// of the Singly Linked List
static Node binarySearch(Node head, int value)
{
Node start = head;
Node last = null;
do
{
// Find Middle
Node mid = middleNode(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 less than mid
else if (mid.data > value)
{
last = mid;
}
// If the value is more than mid.
else
start = mid.next;
} while (last == null || last != start);
// value not present
return null;
}
// Driver Code
public static void main(String[] args)
{
Node head = null;
// Using push() function to
// convert singly linked list
// 10 -> 9 -> 8 -> 7 -> 4 -> 1
head = push(head, 1);
head = push(head, 4);
head = push(head, 7);
head = push(head, 8);
head = push(head, 9);
head = push(head, 10);
int value = 7;
if (binarySearch(head, value) == null)
{
System.out.println("Value not present");
}
else
{
System.out.println("Present");
}
}
}
// This code is contributed by Vivekkumar Singh
Python
# Python code to implement binary search
# on Singly Linked List
# Link list node
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
# function to find out middle element
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
# Function for implementing the Binary
# Search on linked list
def binarySearch(head,value):
start = head
last = None
while True :
# Find middle
mid = middle(start, last)
# If middle is empty
if (mid == None):
return None
# If value is present at middle
if (mid . data == value):
return mid
# If value is more than mid
elif (mid . data < value):
start = mid . next
# If the value is less than mid.
else:
last = mid
if not (last == None or last != start):
break
# value not present
return None
# Driver Code
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)
value = 7
if (binarySearch(head, value) == None):
print("Value not present\n")
else:
print("Present")
# This code is contributed by Arnab Kundu
C#
// C# code to implement binary search
// on Singly Linked List
using System;
// Node Class
public class Node
{
public int data;
public Node next;
// Constructor to create a new node
public Node(int d)
{
data = d;
next = null;
}
}
class BinarySearch
{
// function to insert a node at the beginning
// of the Singly Linked List
static Node push(Node head, int data)
{
Node newNode = new Node(data);
newNode.next = head;
head = newNode;
return head;
}
// Function to find middle element
// using Fast and Slow pointers
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;
}
// function to insert a node at the beginning
// of the Singly Linked List
static Node binarySearch(Node head, int value)
{
Node start = head;
Node last = null;
do
{
// Find Middle
Node mid = middleNode(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 less than mid
else if (mid.data > value)
{
start = mid.next;
}
// If the value is more than mid.
else
last = mid;
} while (last == null || last != start);
// value not present
return null;
}
// Driver Code
public static void Main(String []args)
{
Node head = null;
// Using push() function to
// convert singly linked list
// 10 -> 9 -> 8 -> 7 -> 4 -> 1
head = push(head, 1);
head = push(head, 4);
head = push(head, 7);
head = push(head, 8);
head = push(head, 9);
head = push(head, 10);
int value = 7;
if (binarySearch(head, value) == null)
{
Console.WriteLine("Value not present");
}
else
{
Console.WriteLine("Present");
}
}
}
// This code is contributed by Arnab Kundu
Javascript
<script>
// JavaScript code to implement binary search
// on Singly Linked List
// Node Class
class Node
{
constructor(data)
{
this.data = data;
this.next = null;
}
}
// function to insert a node at the beginning
// of the Singly Linked List
function push(head, data)
{
var newNode = new Node(data);
newNode.next = head;
head = newNode;
return head;
}
// Function to find middle element
// using Fast and Slow pointers
function middleNode(start, last)
{
if (start == null)
return null;
var slow = start;
var fast = start.next;
while (fast != last)
{
fast = fast.next;
if (fast != last)
{
slow = slow.next;
fast = fast.next;
}
}
return slow;
}
// function to insert a node at the beginning
// of the Singly Linked List
function binarySearch(head, value)
{
var start = head;
var last = null;
do
{
// Find Middle
var mid = middleNode(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 less than mid
else if (mid.data > value)
{
start = mid.next;
}
// If the value is more than mid.
else
last = mid;
} while (last == null || last != start);
// value not present
return null;
}
// Driver Code
var head = null;
// Using push() function to
// convert singly linked list
// 10 -> 9 -> 8 -> 7 -> 4 -> 1
head = push(head, 1);
head = push(head, 4);
head = push(head, 7);
head = push(head, 8);
head = push(head, 9);
head = push(head, 10);
var value = 7;
if (binarySearch(head, value) == null)
{
document.write("Value not present");
}
else
{
document.write("Present");
}
</script>
Output
Present
Complexity Analysis:
- Time Complexity: O(N)
- Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
