Binary Search on Singly Linked List
Given a singly linked list and a key, find key using binary search approach.
To perform a Binary search based on Divide and Conquer Algorithm, determination of the middle element is important. Binary Search is usually fast and efficient for arrays because accessing the middle index between two given indices is easy and fast[Time Complexity O[1]]. But memory allocation for the singly linked list is dynamic and non-contiguous, which makes finding the middle element difficult. One approach could be of using skip list, one could be traversing the linked list using one pointer.
Prerequisite: Finding middle of a linked list.
Note: The approach and implementation provided below are to show how Binary Search can be implemented on a linked list. The implementation takes O[n] time.
Approach :
- Here, start node[set to Head of list], and the last node[set to NULL initially] are given.
- Middle is calculated using two pointers approach.
- If middle’s data matches the required value of search, return it.
- Else if middle’s data < value, move to upper half[setting start to middle’s next].
- Else go to lower half[setting last to middle].
- The condition to come out is, either element found or entire list is traversed. When entire list is traversed, last points to start i.e. last -> next == start.
In main function, function InsertAtHead inserts value at the beginning of linked list. Inserting such values[for sake of simplicity] so that the list created is sorted.
Examples :
C++
|
// CPP code to implement binary search
// on Singly Linked List
#include
#include
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 Singaly 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]
{
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 Singaly 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
|
// 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 Singaly 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"];
}
|
Output:
Present
Time Complexity: O[N]
Auxiliary Space: O[1]
Article Tags :
Divide and Conquer
Linked List
Searching
Binary Search
Practice Tags :
Linked List
Searching
Divide and Conquer
Binary Search
Read Full Article
Explanation of using Binary Search
To perform a Binary Search Algorithm on Singly Linked Lists, determination of the middle element is important. Binary Search is fast and efficient because accessing the middle elemen is fast. In arrays, binary search takes O[1] time to access middle element. But memory allocation for the singly linked list is non-contiguous, which makes finding the middle element difficult and time consuming.
The node structure for Linked List is as follows:
// Node structure struct Node { int data; Node* next; };Finding middle element: Two pointer approach
- Traverse the singly linked list using two pointers.
- Move one pointer by one step ahead and the other pointer by two steps.
- When the fast pointer reaches the end of the singly linked list, the slow pointer will reach the middle of the singly linked list.
- Return slow pointer address.