Skip to main content

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




Comment

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