Binary search on singly linked list
Here given code implementation process.
// C program for
// Binary search on singly linked list
#include <stdio.h>
#include <stdlib.h>
// Linked List LinkNode
struct LinkNode
{
int data;
struct LinkNode *next;
};
// Singly linked list
struct SingleLL
{
struct LinkNode *head;
struct LinkNode *tail;
};
// Returns the new linked list
struct SingleLL *newLinkedList()
{
// Create memory of head and tail Nodes
struct SingleLL *sll = (struct SingleLL *) malloc(sizeof(struct SingleLL));
if (sll == NULL)
{
printf("Memory overflow\n");
}
else
{
sll->head = NULL;
sll->tail = NULL;
}
return sll;
}
// Returns the new node of linked list
struct LinkNode *createNode(int data)
{
// Create dynamic node
struct LinkNode *node = (struct LinkNode *) malloc(sizeof(struct LinkNode));
if (node == NULL)
{
printf("Memory overflow to Create LinkNode\n");
}
else
{
// Set initial node value
node->data = data;
node->next = NULL;
}
return node;
}
// Handles the request of adding new node in linked list
void addNode(struct SingleLL *sll, int data)
{
struct LinkNode *node = createNode(data);
if (sll->head == NULL)
{
sll->head = node;
}
else
{
// Append the node at last position
sll->tail->next = node;
}
sll->tail = node;
}
// Display linked list element
void display(struct SingleLL *sll)
{
if (sll->head == NULL)
{
return;
}
struct LinkNode *temp = sll->head;
// iterating linked list elements
while (temp != NULL)
{
printf(" %d →", temp->data);
// Visit to next node
temp = temp->next;
}
printf(" NULL\n");
}
// Returns the middle node in given range
struct LinkNode *findMiddle(struct LinkNode *first, struct LinkNode *last)
{
// Define some auxiliary variables
struct LinkNode *middle = first;
struct LinkNode *temp = first->next;
// Find middle node
while (temp != NULL && temp != last)
{
temp = temp->next;
if (temp != last)
{
// Visit to next node
middle = middle->next;
temp = temp->next;
}
}
return middle;
}
// This is performing the binary search operation
void binarySearch(struct SingleLL *sll, int value)
{
if (sll->head == NULL)
{
printf("\n Empty Linked List");
return;
}
// Define some auxiliary variables
struct LinkNode *last = sll->tail;
struct LinkNode *first = sll->head;
struct LinkNode *result = NULL;
struct LinkNode *mid = sll->head;
if (first->data == value)
{
// When search first element
result = first;
}
if (last->data == value)
{
// When searching last element
result = last;
}
// This loop is detect given element using binary search
while (result == NULL && mid != NULL && first != last)
{
// First find middle element
mid = findMiddle(first, last);
if (mid == NULL)
{
// This is useful when we don't know about initially last node
// and search element is largest then last node
result = NULL;
}
else if (mid->data == value)
{
// When get the find node
result = mid;
}
else if (mid->data > value)
{
// Select new last node
last = mid;
}
else
{
// Select new starting node
first = mid->next;
}
}
if (result != NULL)
{
printf("\n Given element %d are Present", value);
}
else
{
printf("\n Given element %d are not Present", value);
}
}
int main(int argc, char
const *argv[])
{
struct SingleLL *sll = newLinkedList();
// 1 → 7 → 13 → 16 → 25 → 29 → 34 → 39 → NULL
addNode(sll, 1);
addNode(sll, 7);
addNode(sll, 13);
addNode(sll, 16);
addNode(sll, 25);
addNode(sll, 29);
addNode(sll, 34);
addNode(sll, 39);
printf("\n Linked List : ");
display(sll);
// Test Cases
binarySearch(sll, 34);
binarySearch(sll, 20);
binarySearch(sll, 42);
binarySearch(sll, 39);
binarySearch(sll, 16);
return 0;
}
input
Linked List : 1 → 7 → 13 → 16 → 25 → 29 → 34 → 39 → NULL
Given element 34 are Present
Given element 20 are not Present
Given element 42 are not Present
Given element 39 are Present
Given element 16 are Present
/*
Java Program for
Binary search on singly linked list
*/
// Linked list node
class LinkNode
{
public int data;
public LinkNode next;
public LinkNode(int data)
{
this.data = data;
this.next = null;
}
}
public class SingleLL
{
public LinkNode head;
public LinkNode tail;
public SingleLL()
{
this.head = null;
this.tail = null;
}
// Add new Node at end of linked list
public void addNode(int data)
{
LinkNode node = new LinkNode(data);
if (this.head == null)
{
this.head = node;
}
else
{
// Append the node at last position
this.tail.next = node;
}
this.tail = node;
}
// Display linked list element
public void display()
{
if (this.head == null)
{
System.out.println("\n Empty linked list");
return;
}
LinkNode temp = this.head;
//iterating linked list elements
while (temp != null)
{
System.out.print(" " + temp.data + " →");
// Visit to next node
temp = temp.next;
}
System.out.println(" NULL");
}
// Returns the middle node in given range
public LinkNode findMiddle(LinkNode first, LinkNode last)
{
// Define some auxiliary variables
LinkNode middle = first;
LinkNode temp = first.next;
// Find middle node
while (temp != null && temp != last)
{
temp = temp.next;
if (temp != last)
{
// Visit to next node
middle = middle.next;
temp = temp.next;
}
}
return middle;
}
// This is performing the binary search operation
public void binarySearch(int value)
{
if (this.head == null)
{
System.out.print("\n Empty Linked List");
return;
}
// Define some auxiliary variables
LinkNode last = this.tail;
LinkNode first = this.head;
LinkNode result = null;
LinkNode mid = this.head;
if (first.data == value)
{
// When search first element
result = first;
}
if (last.data == value)
{
// When searching last element
result = last;
}
// This loop is detect given element using binary search
while (result == null && mid != null && first != last)
{
// First find middle element
mid = findMiddle(first, last);
if (mid == null)
{
// This is useful when we don't know about initially last node
// and search element is largest then last node
result = null;
}
else if (mid.data == value)
{
// When get the find node
result = mid;
}
else if (mid.data > value)
{
// Select new last node
last = mid;
}
else
{
// Select new starting node
first = mid.next;
}
}
if (result != null)
{
System.out.print("\n Given element " + value + " are Present");
}
else
{
System.out.print("\n Given element " + value + " are not Present");
}
}
public static void main(String[] args)
{
SingleLL sll = new SingleLL();
// Sorted linked list
// 1 → 7 → 13 → 16 → 25 → 29 → 34 → 39 → NULL
sll.addNode(1);
sll.addNode(7);
sll.addNode(13);
sll.addNode(16);
sll.addNode(25);
sll.addNode(29);
sll.addNode(34);
sll.addNode(39);
System.out.print("\n Linked List : ");
sll.display();
// Test Cases
sll.binarySearch(34);
sll.binarySearch(20);
sll.binarySearch(42);
sll.binarySearch(39);
sll.binarySearch(16);
}
}
input
Linked List : 1 → 7 → 13 → 16 → 25 → 29 → 34 → 39 → NULL
Given element 34 are Present
Given element 20 are not Present
Given element 42 are not Present
Given element 39 are Present
Given element 16 are Present
// Include header file
#include <iostream>
using namespace std;
/*
C++ Program for
Binary search on singly linked list
*/
// Linked list node
class LinkNode
{
public:
int data;
LinkNode *next;
LinkNode(int data)
{
this->data = data;
this->next = NULL;
}
};
class SingleLL
{
public:
LinkNode *head;
LinkNode *tail;
SingleLL()
{
this->head = NULL;
this->tail = NULL;
}
// Add new Node at end of linked list
void addNode(int data)
{
LinkNode *node = new LinkNode(data);
if (this->head == NULL)
{
this->head = node;
}
else
{
// Append the node at last position
this->tail->next = node;
}
this->tail = node;
}
// Display linked list element
void display()
{
if (this->head == NULL)
{
cout << "\n Empty linked list" << endl;
return;
}
LinkNode *temp = this->head;
//iterating linked list elements
while (temp != NULL)
{
cout << " " << temp->data << " →";
// Visit to next node
temp = temp->next;
}
cout << " NULL" << endl;
}
// Returns the middle node in given range
LinkNode *findMiddle(LinkNode *first, LinkNode *last)
{
// Define some auxiliary variables
LinkNode *middle = first;
LinkNode *temp = first->next;
// Find middle node
while (temp != NULL && temp != last)
{
temp = temp->next;
if (temp != last)
{
// Visit to next node
middle = middle->next;
temp = temp->next;
}
}
return middle;
}
// This is performing the binary search operation
void binarySearch(int value)
{
if (this->head == NULL)
{
cout << "\n Empty Linked List";
return;
}
// Define some auxiliary variables
LinkNode *last = this->tail;
LinkNode *first = this->head;
LinkNode *result = NULL;
LinkNode *mid = this->head;
if (first->data == value)
{
// When search first element
result = first;
}
if (last->data == value)
{
// When searching last element
result = last;
}
// This loop is detect given element using binary search
while (result == NULL && mid != NULL && first != last)
{
// First find middle element
mid = this->findMiddle(first, last);
if (mid == NULL)
{
// This is useful when we don't know about initially last node
// and search element is largest then last node
result = NULL;
}
else if (mid->data == value)
{
// When get the find node
result = mid;
}
else if (mid->data > value)
{
// Select new last node
last = mid;
}
else
{
// Select new starting node
first = mid->next;
}
}
if (result != NULL)
{
cout << "\n Given element " << value << " are Present";
}
else
{
cout << "\n Given element " << value << " are not Present";
}
}
};
int main()
{
SingleLL *sll = new SingleLL();
// Sorted linked list
// 1 → 7 → 13 → 16 → 25 → 29 → 34 → 39 → NULL
sll->addNode(1);
sll->addNode(7);
sll->addNode(13);
sll->addNode(16);
sll->addNode(25);
sll->addNode(29);
sll->addNode(34);
sll->addNode(39);
cout << "\n Linked List : ";
sll->display();
// Test Cases
sll->binarySearch(34);
sll->binarySearch(20);
sll->binarySearch(42);
sll->binarySearch(39);
sll->binarySearch(16);
return 0;
}
input
Linked List : 1 → 7 → 13 → 16 → 25 → 29 → 34 → 39 → NULL
Given element 34 are Present
Given element 20 are not Present
Given element 42 are not Present
Given element 39 are Present
Given element 16 are Present
// Include namespace system
using System;
/*
Csharp Program for
Binary search on singly linked list
*/
// Linked list node
public class LinkNode
{
public int data;
public LinkNode next;
public LinkNode(int data)
{
this.data = data;
this.next = null;
}
}
public class SingleLL
{
public LinkNode head;
public LinkNode tail;
public SingleLL()
{
this.head = null;
this.tail = null;
}
// Add new Node at end of linked list
public void addNode(int data)
{
LinkNode node = new LinkNode(data);
if (this.head == null)
{
this.head = node;
}
else
{
// Append the node at last position
this.tail.next = node;
}
this.tail = node;
}
// Display linked list element
public void display()
{
if (this.head == null)
{
Console.WriteLine("\n Empty linked list");
return;
}
LinkNode temp = this.head;
//iterating linked list elements
while (temp != null)
{
Console.Write(" " + temp.data + " →");
// Visit to next node
temp = temp.next;
}
Console.WriteLine(" NULL");
}
// Returns the middle node in given range
public LinkNode findMiddle(LinkNode first, LinkNode last)
{
// Define some auxiliary variables
LinkNode middle = first;
LinkNode temp = first.next;
// Find middle node
while (temp != null && temp != last)
{
temp = temp.next;
if (temp != last)
{
// Visit to next node
middle = middle.next;
temp = temp.next;
}
}
return middle;
}
// This is performing the binary search operation
public void binarySearch(int value)
{
if (this.head == null)
{
Console.Write("\n Empty Linked List");
return;
}
// Define some auxiliary variables
LinkNode last = this.tail;
LinkNode first = this.head;
LinkNode result = null;
LinkNode mid = this.head;
if (first.data == value)
{
// When search first element
result = first;
}
if (last.data == value)
{
// When searching last element
result = last;
}
// This loop is detect given element using binary search
while (result == null && mid != null && first != last)
{
// First find middle element
mid = this.findMiddle(first, last);
if (mid == null)
{
// This is useful when we don't know about initially last node
// and search element is largest then last node
result = null;
}
else if (mid.data == value)
{
// When get the find node
result = mid;
}
else if (mid.data > value)
{
// Select new last node
last = mid;
}
else
{
// Select new starting node
first = mid.next;
}
}
if (result != null)
{
Console.Write("\n Given element " + value + " are Present");
}
else
{
Console.Write("\n Given element " + value + " are not Present");
}
}
public static void Main(String[] args)
{
SingleLL sll = new SingleLL();
// Sorted linked list
// 1 → 7 → 13 → 16 → 25 → 29 → 34 → 39 → NULL
sll.addNode(1);
sll.addNode(7);
sll.addNode(13);
sll.addNode(16);
sll.addNode(25);
sll.addNode(29);
sll.addNode(34);
sll.addNode(39);
Console.Write("\n Linked List : ");
sll.display();
// Test Cases
sll.binarySearch(34);
sll.binarySearch(20);
sll.binarySearch(42);
sll.binarySearch(39);
sll.binarySearch(16);
}
}
input
Linked List : 1 → 7 → 13 → 16 → 25 → 29 → 34 → 39 → NULL
Given element 34 are Present
Given element 20 are not Present
Given element 42 are not Present
Given element 39 are Present
Given element 16 are Present
<?php
/*
Php Program for
Binary search on singly linked list
*/
// Linked list node
class LinkNode
{
public $data;
public $next;
public function __construct($data)
{
$this->data = $data;
$this->next = NULL;
}
}
class SingleLL
{
public $head;
public $tail;
public function __construct()
{
$this->head = NULL;
$this->tail = NULL;
}
// Add new Node at end of linked list
public function addNode($data)
{
$node = new LinkNode($data);
if ($this->head == NULL)
{
$this->head = $node;
}
else
{
// Append the node at last position
$this->tail->next = $node;
}
$this->tail = $node;
}
// Display linked list element
public function display()
{
if ($this->head == NULL)
{
echo("\n Empty linked list".
"\n");
return;
}
$temp = $this->head;
//iterating linked list elements
while ($temp != NULL)
{
echo(" ".$temp->data.
" →");
// Visit to next node
$temp = $temp->next;
}
echo(" NULL".
"\n");
}
// Returns the middle node in given range
public function findMiddle($first, $last)
{
// Define some auxiliary variables
$middle = $first;
$temp = $first->next;
// Find middle node
while ($temp != NULL && $temp != $last)
{
$temp = $temp->next;
if ($temp != $last)
{
// Visit to next node
$middle = $middle->next;
$temp = $temp->next;
}
}
return $middle;
}
// This is performing the binary search operation
public function binarySearch($value)
{
if ($this->head == NULL)
{
echo("\n Empty Linked List");
return;
}
// Define some auxiliary variables
$last = $this->tail;
$first = $this->head;
$result = NULL;
$mid = $this->head;
if ($first->data == $value)
{
// When search first element
$result = $first;
}
if ($last->data == $value)
{
// When searching last element
$result = $last;
}
// This loop is detect given element using binary search
while ($result == NULL && $mid != NULL && $first != $last)
{
// First find middle element
$mid = $this->findMiddle($first, $last);
if ($mid == NULL)
{
// This is useful when we don't know about initially last node
// and search element is largest then last node
$result = NULL;
}
else if ($mid->data == $value)
{
// When get the find node
$result = $mid;
}
else if ($mid->data > $value)
{
// Select new last node
$last = $mid;
}
else
{
// Select new starting node
$first = $mid->next;
}
}
if ($result != NULL)
{
echo("\n Given element ".$value.
" are Present");
}
else
{
echo("\n Given element ".$value.
" are not Present");
}
}
}
function main()
{
$sll = new SingleLL();
// Sorted linked list
// 1 → 7 → 13 → 16 → 25 → 29 → 34 → 39 → NULL
$sll->addNode(1);
$sll->addNode(7);
$sll->addNode(13);
$sll->addNode(16);
$sll->addNode(25);
$sll->addNode(29);
$sll->addNode(34);
$sll->addNode(39);
echo("\n Linked List : ");
$sll->display();
// Test Cases
$sll->binarySearch(34);
$sll->binarySearch(20);
$sll->binarySearch(42);
$sll->binarySearch(39);
$sll->binarySearch(16);
}
main();
input
Linked List : 1 → 7 → 13 → 16 → 25 → 29 → 34 → 39 → NULL
Given element 34 are Present
Given element 20 are not Present
Given element 42 are not Present
Given element 39 are Present
Given element 16 are Present
/*
Node JS Program for
Binary search on singly linked list
*/
// Linked list node
class LinkNode
{
constructor(data)
{
this.data = data;
this.next = null;
}
}
class SingleLL
{
constructor()
{
this.head = null;
this.tail = null;
}
// Add new Node at end of linked list
addNode(data)
{
var node = new LinkNode(data);
if (this.head == null)
{
this.head = node;
}
else
{
// Append the node at last position
this.tail.next = node;
}
this.tail = node;
}
// Display linked list element
display()
{
if (this.head == null)
{
console.log("\n Empty linked list");
return;
}
var temp = this.head;
//iterating linked list elements
while (temp != null)
{
process.stdout.write(" " + temp.data + " →");
// Visit to next node
temp = temp.next;
}
console.log(" NULL");
}
// Returns the middle node in given range
findMiddle(first, last)
{
// Define some auxiliary variables
var middle = first;
var temp = first.next;
// Find middle node
while (temp != null && temp != last)
{
temp = temp.next;
if (temp != last)
{
// Visit to next node
middle = middle.next;
temp = temp.next;
}
}
return middle;
}
// This is performing the binary search operation
binarySearch(value)
{
if (this.head == null)
{
process.stdout.write("\n Empty Linked List");
return;
}
// Define some auxiliary variables
var last = this.tail;
var first = this.head;
var result = null;
var mid = this.head;
if (first.data == value)
{
// When search first element
result = first;
}
if (last.data == value)
{
// When searching last element
result = last;
}
// This loop is detect given element using binary search
while (result == null && mid != null && first != last)
{
// First find middle element
mid = this.findMiddle(first, last);
if (mid == null)
{
// This is useful when we don't know about initially last node
// and search element is largest then last node
result = null;
}
else if (mid.data == value)
{
// When get the find node
result = mid;
}
else if (mid.data > value)
{
// Select new last node
last = mid;
}
else
{
// Select new starting node
first = mid.next;
}
}
if (result != null)
{
process.stdout.write("\n Given element " + value + " are Present");
}
else
{
process.stdout.write("\n Given element " + value + " are not Present");
}
}
}
function main()
{
var sll = new SingleLL();
// Sorted linked list
// 1 → 7 → 13 → 16 → 25 → 29 → 34 → 39 → NULL
sll.addNode(1);
sll.addNode(7);
sll.addNode(13);
sll.addNode(16);
sll.addNode(25);
sll.addNode(29);
sll.addNode(34);
sll.addNode(39);
process.stdout.write("\n Linked List : ");
sll.display();
// Test Cases
sll.binarySearch(34);
sll.binarySearch(20);
sll.binarySearch(42);
sll.binarySearch(39);
sll.binarySearch(16);
}
main();
input
Linked List : 1 → 7 → 13 → 16 → 25 → 29 → 34 → 39 → NULL
Given element 34 are Present
Given element 20 are not Present
Given element 42 are not Present
Given element 39 are Present
Given element 16 are Present
# Python 3 Program for
# Binary search on singly linked list
# Linked list node
class LinkNode :
def __init__(self, data) :
self.data = data
self.next = None
class SingleLL :
def __init__(self) :
self.head = None
self.tail = None
# Add new Node at end of linked list
def addNode(self, data) :
node = LinkNode(data)
if (self.head == None) :
self.head = node
else :
# Append the node at last position
self.tail.next = node
self.tail = node
# Display linked list element
def display(self) :
if (self.head == None) :
print("\n Empty linked list")
return
temp = self.head
# iterating linked list elements
while (temp != None) :
print("", temp.data ,"→", end = "")
# Visit to next node
temp = temp.next
print(" NULL")
# Returns the middle node in given range
def findMiddle(self, first, last) :
# Define some auxiliary variables
middle = first
temp = first.next
# Find middle node
while (temp != None and temp != last) :
temp = temp.next
if (temp != last) :
# Visit to next node
middle = middle.next
temp = temp.next
return middle
# This is performing the binary search operation
def binarySearch(self, value) :
if (self.head == None) :
print("\n Empty Linked List", end = "")
return
# Define some auxiliary variables
last = self.tail
first = self.head
result = None
mid = self.head
if (first.data == value) :
# When search first element
result = first
if (last.data == value) :
# When searching last element
result = last
# This loop is detect given element using binary search
while (result == None and mid != None and first != last) :
# First find middle element
mid = self.findMiddle(first, last)
if (mid == None) :
# This is useful when we don't know about initially last node
# and search element is largest then last node
result = None
elif (mid.data == value) :
# When get the find node
result = mid
elif (mid.data > value) :
# Select new last node
last = mid
else :
# Select new starting node
first = mid.next
if (result != None) :
print("\n Given element", value ,"are Present", end = "")
else :
print("\n Given element", value ,"are not Present", end = "")
def main() :
sll = SingleLL()
# Sorted linked list
# 1 → 7 → 13 → 16 → 25 → 29 → 34 → 39 → NULL
sll.addNode(1)
sll.addNode(7)
sll.addNode(13)
sll.addNode(16)
sll.addNode(25)
sll.addNode(29)
sll.addNode(34)
sll.addNode(39)
print("\n Linked List : ", end = "")
sll.display()
# Test Cases
sll.binarySearch(34)
sll.binarySearch(20)
sll.binarySearch(42)
sll.binarySearch(39)
sll.binarySearch(16)
if __name__ == "__main__": main()
input
Linked List : 1 → 7 → 13 → 16 → 25 → 29 → 34 → 39 → NULL
Given element 34 are Present
Given element 20 are not Present
Given element 42 are not Present
Given element 39 are Present
Given element 16 are Present
# Ruby Program for
# Binary search on singly linked list
# Linked list node
class LinkNode
# Define the accessor and reader of class LinkNode
attr_reader :data, :next
attr_accessor :data, :next
def initialize(data)
self.data = data
self.next = nil
end
end
class SingleLL
# Define the accessor and reader of class SingleLL
attr_reader :head, :tail
attr_accessor :head, :tail
def initialize()
self.head = nil
self.tail = nil
end
# Add new Node at end of linked list
def addNode(data)
node = LinkNode.new(data)
if (self.head == nil)
self.head = node
else
# Append the node at last position
self.tail.next = node
end
self.tail = node
end
# Display linked list element
def display()
if (self.head == nil)
print("\n Empty linked list", "\n")
return
end
temp = self.head
# iterating linked list elements
while (temp != nil)
print(" ", temp.data ," →")
# Visit to next node
temp = temp.next
end
print(" NULL", "\n")
end
# Returns the middle node in given range
def findMiddle(first, last)
# Define some auxiliary variables
middle = first
temp = first.next
# Find middle node
while (temp != nil && temp != last)
temp = temp.next
if (temp != last)
# Visit to next node
middle = middle.next
temp = temp.next
end
end
return middle
end
# This is performing the binary search operation
def binarySearch(value)
if (self.head == nil)
print("\n Empty Linked List")
return
end
# Define some auxiliary variables
last = self.tail
first = self.head
result = nil
mid = self.head
if (first.data == value)
# When search first element
result = first
end
if (last.data == value)
# When searching last element
result = last
end
# This loop is detect given element using binary search
while (result == nil && mid != nil && first != last)
# First find middle element
mid = self.findMiddle(first, last)
if (mid == nil)
# This is useful when we don't know about initially last node
# and search element is largest then last node
result = nil
elseif(mid.data == value)
# When get the find node
result = mid
elseif(mid.data > value)
# Select new last node
last = mid
else
# Select new starting node
first = mid.next
end
end
if (result != nil)
print("\n Given element ", value ," are Present")
else
print("\n Given element ", value ," are not Present")
end
end
end
def main()
sll = SingleLL.new()
# Sorted linked list
# 1 → 7 → 13 → 16 → 25 → 29 → 34 → 39 → NULL
sll.addNode(1)
sll.addNode(7)
sll.addNode(13)
sll.addNode(16)
sll.addNode(25)
sll.addNode(29)
sll.addNode(34)
sll.addNode(39)
print("\n Linked List : ")
sll.display()
# Test Cases
sll.binarySearch(34)
sll.binarySearch(20)
sll.binarySearch(42)
sll.binarySearch(39)
sll.binarySearch(16)
end
main()
input
Linked List : 1 → 7 → 13 → 16 → 25 → 29 → 34 → 39 → NULL
Given element 34 are not Present
Given element 20 are not Present
Given element 42 are not Present
Given element 39 are Present
Given element 16 are not Present
/*
Scala Program for
Binary search on singly linked list
*/
// Linked list node
class LinkNode(var data: Int , var next: LinkNode)
{
def this(data: Int)
{
this(data,null);
}
}
class SingleLL(var head: LinkNode , var tail: LinkNode)
{
def this()
{
this(null,null);
}
// Add new Node at end of linked list
def addNode(data: Int): Unit = {
var node: LinkNode = new LinkNode(data);
if (this.head == null)
{
this.head = node;
}
else
{
// Append the node at last position
this.tail.next = node;
}
this.tail = node;
}
// Display linked list element
def display(): Unit = {
if (this.head == null)
{
println("\n Empty linked list");
return;
}
var temp: LinkNode = this.head;
//iterating linked list elements
while (temp != null)
{
print(" " + temp.data + " →");
// Visit to next node
temp = temp.next;
}
println(" NULL");
}
// Returns the middle node in given range
def findMiddle(first: LinkNode, last: LinkNode): LinkNode = {
// Define some auxiliary variables
var middle: LinkNode = first;
var temp: LinkNode = first.next;
// Find middle node
while (temp != null && temp != last)
{
temp = temp.next;
if (temp != last)
{
// Visit to next node
middle = middle.next;
temp = temp.next;
}
}
return middle;
}
// This is performing the binary search operation
def binarySearch(value: Int): Unit = {
if (this.head == null)
{
print("\n Empty Linked List");
return;
}
// Define some auxiliary variables
var last: LinkNode = this.tail;
var first: LinkNode = this.head;
var result: LinkNode = null;
var mid: LinkNode = this.head;
if (first.data == value)
{
// When search first element
result = first;
}
if (last.data == value)
{
// When searching last element
result = last;
}
// This loop is detect given element using binary search
while (result == null && mid != null && first != last)
{
// First find middle element
mid = findMiddle(first, last);
if (mid == null)
{
// This is useful when we don't know about initially last node
// and search element is largest then last node
result = null;
}
else if (mid.data == value)
{
// When get the find node
result = mid;
}
else if (mid.data > value)
{
// Select new last node
last = mid;
}
else
{
// Select new starting node
first = mid.next;
}
}
if (result != null)
{
print("\n Given element " + value + " are Present");
}
else
{
print("\n Given element " + value + " are not Present");
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
var sll: SingleLL = new SingleLL();
// Sorted linked list
// 1 → 7 → 13 → 16 → 25 → 29 → 34 → 39 → NULL
sll.addNode(1);
sll.addNode(7);
sll.addNode(13);
sll.addNode(16);
sll.addNode(25);
sll.addNode(29);
sll.addNode(34);
sll.addNode(39);
print("\n Linked List : ");
sll.display();
// Test Cases
sll.binarySearch(34);
sll.binarySearch(20);
sll.binarySearch(42);
sll.binarySearch(39);
sll.binarySearch(16);
}
}
input
Linked List : 1 → 7 → 13 → 16 → 25 → 29 → 34 → 39 → NULL
Given element 34 are Present
Given element 20 are not Present
Given element 42 are not Present
Given element 39 are Present
Given element 16 are Present
/*
Swift 4 Program for
Binary search on singly linked list
*/
// Linked list node
class LinkNode
{
var data: Int;
var next: LinkNode? ;
init(_ data: Int)
{
self.data = data;
self.next = nil;
}
}
class SingleLL
{
var head: LinkNode? ;
var tail: LinkNode? ;
init()
{
self.head = nil;
self.tail = nil;
}
// Add new Node at end of linked list
func addNode(_ data: Int)
{
let node: LinkNode = LinkNode(data);
if (self.head == nil)
{
self.head = node;
}
else
{
// Append the node at last position
self.tail!.next = node;
}
self.tail = node;
}
// Display linked list element
func display()
{
if (self.head == nil)
{
print("\n Empty linked list");
return;
}
var temp: LinkNode? = self.head;
//iterating linked list elements
while (temp != nil)
{
print(" ", temp!.data ," →", terminator: "");
// Visit to next node
temp = temp!.next;
}
print(" NULL");
}
// Returns the middle node in given range
func findMiddle(_ first: LinkNode? , _ last : LinkNode? )->LinkNode?
{
// Define some auxiliary variables
var middle: LinkNode? = first;
var temp: LinkNode? = first!.next;
// Find middle node
while (temp != nil && !(temp === last))
{
temp = temp!.next;
if (!(temp === last))
{
// Visit to next node
middle = middle!.next;
temp = temp!.next;
}
}
return middle;
}
// This is performing the binary search operation
func binarySearch(_ value: Int)
{
if (self.head == nil)
{
print("\n Empty Linked List", terminator: "");
return;
}
// Define some auxiliary variables
var last: LinkNode? = self.tail;
var first: LinkNode? = self.head;
var result: LinkNode? = nil;
var mid: LinkNode? = self.head;
if (first!.data == value)
{
// When search first element
result = first;
}
if (last!.data == value)
{
// When searching last element
result = last;
}
// This loop is detect given element using binary search
while (result == nil && mid != nil && !(first === last))
{
// First find middle element
mid = self.findMiddle(first, last);
if (mid == nil)
{
// This is useful when we don't know about initially last node
// and search element is largest then last node
result = nil;
}
else if (mid!.data == value)
{
// When get the find node
result = mid;
}
else if (mid!.data > value)
{
// Select new last node
last = mid;
}
else
{
// Select new starting node
first = mid!.next;
}
}
if (result != nil)
{
print(" Given element ", value ," are Present");
}
else
{
print(" Given element ", value ," are not Present");
}
}
}
func main()
{
let sll: SingleLL = SingleLL();
// Sorted linked list
// 1 → 7 → 13 → 16 → 25 → 29 → 34 → 39 → NULL
sll.addNode(1);
sll.addNode(7);
sll.addNode(13);
sll.addNode(16);
sll.addNode(25);
sll.addNode(29);
sll.addNode(34);
sll.addNode(39);
print("\n Linked List : ", terminator: "");
sll.display();
// Test Cases
sll.binarySearch(34);
sll.binarySearch(20);
sll.binarySearch(42);
sll.binarySearch(39);
sll.binarySearch(16);
}
main();
input
Linked List : 1 → 7 → 13 → 16 → 25 → 29 → 34 → 39 → NULL
Given element 34 are Present
Given element 20 are not Present
Given element 42 are not Present
Given element 39 are Present
Given element 16 are Present
/*
Kotlin Program for
Binary search on singly linked list
*/
// Linked list node
class LinkNode
{
var data: Int;
var next: LinkNode ? ;
constructor(data: Int)
{
this.data = data;
this.next = null;
}
}
class SingleLL
{
var head: LinkNode ? ;
var tail: LinkNode ? ;
constructor()
{
this.head = null;
this.tail = null;
}
// Add new Node at end of linked list
fun addNode(data: Int): Unit
{
val node: LinkNode = LinkNode(data);
if (this.head == null)
{
this.head = node;
}
else
{
// Append the node at last position
this.tail?.next = node;
}
this.tail = node;
}
// Display linked list element
fun display(): Unit
{
if (this.head == null)
{
println("\n Empty linked list");
return;
}
var temp: LinkNode ? = this.head;
//iterating linked list elements
while (temp != null)
{
print(" " + temp.data + " →");
// Visit to next node
temp = temp.next;
}
println(" NULL");
}
// Returns the middle node in given range
fun findMiddle(first: LinkNode ? , last : LinkNode ? ): LinkNode ?
{
// Define some auxiliary variables
var middle: LinkNode ? = first;
var temp: LinkNode ? = first?.next;
// Find middle node
while (temp != null && temp != last)
{
temp = temp.next;
if (temp != last)
{
// Visit to next node
middle = middle?.next;
temp = temp?.next;
}
}
return middle;
}
// This is performing the binary search operation
fun binarySearch(value: Int): Unit
{
if (this.head == null)
{
print("\n Empty Linked List");
return;
}
// Define some auxiliary variables
var last: LinkNode ? = this.tail;
var first: LinkNode ? = this.head;
var result: LinkNode ? = null;
var mid: LinkNode ? = this.head;
if (first!!.data == value)
{
// When search first element
result = first;
}
if (last!!.data == value)
{
// When searching last element
result = last;
}
// This loop is detect given element using binary search
while (result == null && mid != null && first != last)
{
// First find middle element
mid = this.findMiddle(first, last);
if (mid == null)
{
// This is useful when we don't know about initially last node
// and search element is largest then last node
result = null;
}
else if (mid.data == value)
{
// When get the find node
result = mid;
}
else if (mid.data > value)
{
// Select new last node
last = mid;
}
else
{
// Select new starting node
first = mid.next;
}
}
if (result != null)
{
print("\n Given element " + value + " are Present");
}
else
{
print("\n Given element " + value + " are not Present");
}
}
}
fun main(args: Array < String > ): Unit
{
val sll: SingleLL = SingleLL();
// Sorted linked list
// 1 → 7 → 13 → 16 → 25 → 29 → 34 → 39 → NULL
sll.addNode(1);
sll.addNode(7);
sll.addNode(13);
sll.addNode(16);
sll.addNode(25);
sll.addNode(29);
sll.addNode(34);
sll.addNode(39);
print("\n Linked List : ");
sll.display();
// Test Cases
sll.binarySearch(34);
sll.binarySearch(20);
sll.binarySearch(42);
sll.binarySearch(39);
sll.binarySearch(16);
}
input
Linked List : 1 → 7 → 13 → 16 → 25 → 29 → 34 → 39 → NULL
Given element 34 are Present
Given element 20 are not Present
Given element 42 are not Present
Given element 39 are Present
Given element 16 are Present
Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.
New Comment