Posted on by Kalkicode
Code Divide And Conquer

# Binary search on singly linked list

In computer science, binary search is a classic algorithm used to quickly locate a specific element in a sorted list of elements. However, binary search is typically performed on arrays or contiguous data structures, as it relies on random access to elements. In this article, we will explore how to perform binary search on a singly linked list, which is a non-contiguous data structure.

Problem Statement:

Given a singly linked list and a target value, we want to determine if the target value is present in the list. If the value is found, we will output a positive result, otherwise, we will output a negative result. The goal is to perform this search efficiently by applying the principles of binary search on the linked list.

Pseudocode Algorithm:

```1. Start with the first and last nodes of the linked list as initial search boundaries.
2. Set the result pointer to NULL initially.
3. Repeat the following steps while the result is not found and there are more than two nodes between the first and last boundaries:
- Find the middle node between the first and last boundaries.
- If the middle node's data matches the target value, set the result pointer to the middle node and exit the loop.
- If the middle node's data is greater than the target value, update the last boundary to the middle node.
- If the middle node's data is less than the target value, update the first boundary to the node next to the middle node.
4. Check if the result pointer is not NULL:
- If it's not NULL, output "Given element [value] is Present."
- If it's NULL, output "Given element [value] is not Present."
```

## Code Solution

``````// C program for
// Binary search on singly linked list
#include <stdio.h>
#include <stdlib.h>

{
int data;
};
struct SingleLL
{
};
// Returns the new linked list
{
// 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->tail = NULL;
}
return sll;
}
// Returns the new node of linked list
{
// Create dynamic node
if (node == NULL)
{
}
else
{
// Set initial node value
node->data = data;
node->next = NULL;
}
return node;
}
void addNode(struct SingleLL *sll, int data)
{
{
}
else
{
// Append the node at last position
sll->tail->next = node;
}
sll->tail = node;
}
void display(struct SingleLL *sll)
{
{
return;
}
while (temp != NULL)
{
printf(" %d →", temp->data);
// Visit to next node
temp = temp->next;
}
printf(" NULL\n");
}
// Returns the middle node in given range
{
// Define some auxiliary variables
// 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)
{
{
return;
}
// Define some auxiliary variables
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[])
{
//  1 → 7 → 13 → 16 → 25 → 29 → 34 → 39 → NULL
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
*/
{
public int data;
{
this.data = data;
this.next = null;
}
}
public class SingleLL
{
public SingleLL()
{
this.tail = null;
}
{
{
}
else
{
// Append the node at last position
this.tail.next = node;
}
this.tail = node;
}
public void display()
{
{
return;
}
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
{
// Define some auxiliary variables
// 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)
{
{
return;
}
// Define some auxiliary variables
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();
//  1 → 7 → 13 → 16 → 25 → 29 → 34 → 39 → NULL
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
*/
{
public:
int data;
{
this->data = data;
this->next = NULL;
}
};
class SingleLL
{
public:
SingleLL()
{
this->tail = NULL;
}
{
{
}
else
{
// Append the node at last position
this->tail->next = node;
}
this->tail = node;
}
void display()
{
{
cout << "\n Empty linked list" << endl;
return;
}
while (temp != NULL)
{
cout << " " << temp->data << " →";
// Visit to next node
temp = temp->next;
}
cout << " NULL" << endl;
}
// Returns the middle node in given range
{
// Define some auxiliary variables
// 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)
{
{
cout << "\n Empty Linked List";
return;
}
// Define some auxiliary variables
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();
//  1 → 7 → 13 → 16 → 25 → 29 → 34 → 39 → NULL
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
*/
{
public int data;
{
this.data = data;
this.next = null;
}
}
public class SingleLL
{
public SingleLL()
{
this.tail = null;
}
{
{
}
else
{
// Append the node at last position
this.tail.next = node;
}
this.tail = node;
}
public void display()
{
{
return;
}
while (temp != null)
{
Console.Write(" " + temp.data + " →");
// Visit to next node
temp = temp.next;
}
Console.WriteLine(" NULL");
}
// Returns the middle node in given range
{
// Define some auxiliary variables
// 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)
{
{
return;
}
// Define some auxiliary variables
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();
//  1 → 7 → 13 → 16 → 25 → 29 → 34 → 39 → NULL
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
*/
{
public \$data;
public \$next;
public	function __construct(\$data)
{
\$this->data = \$data;
\$this->next = NULL;
}
}
class SingleLL
{
public \$tail;
public	function __construct()
{
\$this->tail = NULL;
}
{
{
}
else
{
// Append the node at last position
\$this->tail->next = \$node;
}
\$this->tail = \$node;
}
public	function display()
{
{
"\n");
return;
}
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)
{
{
return;
}
// Define some auxiliary variables
\$last = \$this->tail;
\$result = NULL;
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();
//  1 → 7 → 13 → 16 → 25 → 29 → 34 → 39 → NULL
\$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
*/
{
constructor(data)
{
this.data = data;
this.next = null;
}
}
class SingleLL
{
constructor()
{
this.tail = null;
}
{
{
}
else
{
// Append the node at last position
this.tail.next = node;
}
this.tail = node;
}
display()
{
{
return;
}
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)
{
{
return;
}
// Define some auxiliary variables
var last = this.tail;
var result = null;
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();
//  1 → 7 → 13 → 16 → 25 → 29 → 34 → 39 → NULL
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

def __init__(self, data) :
self.data = data
self.next = None

class SingleLL :
def __init__(self) :
self.tail = None

else :
#  Append the node at last position
self.tail.next = node

self.tail = node

def display(self) :
return

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) :
print("\n Empty Linked List", end = "")
return

#  Define some auxiliary variables
last = self.tail
result = None
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()
#   1 → 7 → 13 → 16 → 25 → 29 → 34 → 39 → NULL
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

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
def initialize()
self.tail = nil
end

else
#  Append the node at last position
self.tail.next = node
end

self.tail = node
end

def display()
return
end

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)
return
end

#  Define some auxiliary variables
last = self.tail
result = nil
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()
#   1 → 7 → 13 → 16 → 25 → 29 → 34 → 39 → NULL
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
*/
{
def this(data: Int)
{
this(data,null);
}
}
{
def this()
{
this(null,null);
}
def addNode(data: Int): Unit = {
{
}
else
{
// Append the node at last position
this.tail.next = node;
}
this.tail = node;
}
def display(): Unit = {
{
return;
}
while (temp != null)
{
print(" " + temp.data + " →");
// Visit to next node
temp = temp.next;
}
println(" NULL");
}
// Returns the middle node in given range
// Define some auxiliary variables
// 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 = {
{
return;
}
// Define some auxiliary variables
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();
//  1 → 7 → 13 → 16 → 25 → 29 → 34 → 39 → NULL
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
*/
{
var data: Int;
init(_ data: Int)
{
self.data = data;
self.next = nil;
}
}
class SingleLL
{
init()
{
self.tail = nil;
}
{
{
}
else
{
// Append the node at last position
self.tail!.next = node;
}
self.tail = node;
}
func display()
{
{
return;
}
while (temp  != nil)
{
print(" ", temp!.data ," →", terminator: "");
// Visit to next node
temp = temp!.next;
}
print(" NULL");
}
// Returns the middle node in given range
{
// Define some auxiliary variables
// 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)
{
{
print("\n Empty Linked List", terminator: "");
return;
}
// Define some auxiliary variables
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();
//  1 → 7 → 13 → 16 → 25 → 29 → 34 → 39 → NULL
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
*/
{
var data: Int;
constructor(data: Int)
{
this.data = data;
this.next = null;
}
}
class SingleLL
{
constructor()
{
this.tail = null;
}
{
{
}
else
{
// Append the node at last position
this.tail?.next = node;
}
this.tail = node;
}
fun display(): Unit
{
{
return;
}
while (temp != null)
{
print(" " + temp.data + " →");
// Visit to next node
temp = temp.next;
}
println(" NULL");
}
// Returns the middle node in given range
{
// 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
{
{
return;
}
// Define some auxiliary variables
var last: LinkNode ? = this.tail;
var result: LinkNode ? = null;
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();
//  1 → 7 → 13 → 16 → 25 → 29 → 34 → 39 → NULL
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``````

Explanation:

To perform binary search on a singly linked list, we start with the first and last nodes as search boundaries. We use the findMiddle() function to find the middle node between these boundaries. This function helps us split the search range in half, similar to how binary search is done on arrays.

We iterate through the linked list until we find the target value or narrow down the search boundaries to only two nodes. If the middle node's data matches the target value, we set the result pointer to the middle node and exit the loop. If the middle node's data is greater than the target value, we update the last boundary to the middle node, effectively discarding the upper half of the search range. If the middle node's data is less than the target value, we update the first boundary to the node next to the middle node, discarding the lower half of the search range.

After the loop, we check if the result pointer is not NULL. If it's not NULL, it means that the target value was found in the linked list, and we output "Given element [value] is Present." If the result pointer is NULL, it means the target value was not found, and we output "Given element [value] is not Present."

Resultant Output Explanation:

The given linked list is: 1 → 7 → 13 → 16 → 25 → 29 → 34 → 39 → NULL. We perform binary search for various target values:

• For target value 34: The result is found, so we output "Given element 34 is Present."
• For target value 20: The result is not found, so we output "Given element 20 is not Present."
• For target value 42: The result is not found, so we output "Given element 42 is not Present."
• For target value 39: The result is found, so we output "Given element 39 is Present."
• For target value 16: The result is found, so we output "Given element 16 is Present."

Time Complexity:

The time complexity of binary search on a singly linked list is O(log n), where n is the number of elements in the linked list. This is because, at each step, we reduce the search range by half. The space complexity is O(1) since we only use a few auxiliary variables to perform the search.

## 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.

Categories
Relative Post