1.
Introduction
2.
Why do we use a binary search?
3.
Problem Statement
3.1.
Example
3.1.1.
Input
3.1.2.
Output
3.1.3.
Explanation
3.2.
Analysis of the problem statement
4.
Approach
4.1.
Dry Run
4.2.
C++ Implementation
4.3.
Java Implementation
4.4.
Python Implementation
4.5.
Output
4.6.
Time Complexity
4.7.
Space Complexity
5.
5.1.
5.2.
What is binary search?
5.3.
What is the time complexity of performing a binary search on linked lists?
5.4.
What is the space complexity of performing a binary search on linked lists?
5.5.
Why is a binary search on arrays better than linked lists?
6.
Conclusion
Last Updated: Mar 27, 2024
Easy

# Binary Search on Linked List

Shubham Agarwal
Data structures & algorithms (Beginner to Intermediate)
Free guided path
13 chapters
99+ problems

## Introduction

Hey Ninjas, today we will discuss a very useful method for searching, binary search. We will see the use of binary search on the linked lists.

We know that binary search is useful for searching a target element in a collection of sorted data.

Recommended Topic, Floyds Algorithm and Rabin Karp Algorithm.

## Why do we use a binary search?

We use binary search because, in this, it is not required to iterate over every node. We only search for the target value in a possible range. To be more specific, we deploy a divide-and-conquer approach. Through this approach, the search space becomes half at each step until we find the target element or the search space is exhausted(element not present). Whereas in a linear search, we iterate over all the linked list nodes and compare the data with the target. If they are equal, the target is present, and we end the traversal. Otherwise, continue until we find the target or reach the end of the list.

There is one constraint to be able to perform binary search and that is the data structure on which the binary search is to be done must contain elements in sorted order.

If you are unaware of binary search, please read Introduction To Binary Search Algorithm before moving further. Also, check out Linked Lists to quickly brush up on linked lists.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

## Problem Statement

You are given a sorted, singly linked list of integers and a target element. You need to find whether the target element is present in the linked list or not.

### Example

Given a target value and a sorted linked list. Find whether the element is present in the linked list or not.

Target = 16

Target found

#### Explanation

For target=16 since 16 is there in the linked list, the output will be “Target found.”

### Analysis of the problem statement

If we analyze the problem statement, we get that it says we need to search for a target value in the linked list. So if we use the traditional linear search technique, it will be very costly to us in terms of time. As we read above, we must iterate through every node in a linear search. So in this article, we will learn about a better approach to solving this problem. This approach will use the technique of binary search.

As in binary search, we need to know the middle element. There is a prerequisite to this problem, that is, to find the middle node of a linked list. So, please consider reading the article Finding the Middle Node of a Linked List, as after understanding this concept, the binary search algorithm will be a cakewalk.

## Approach

• Define two pointers - start and end. Start points to the head of the linked list, and endpoints to the last node of the linked list.

• Find the middle node of the linked list using the approach of the fast and slow pointers. Let the mid pointer point it.

• Compare the value of the middle node with the target element. There can be three cases-
• If mid->value == target: then print “Target found” and break the loop.

• If mid->value  < target: then it implies that the target lies in the right half of the list as its value is greater than that of the middle node. So, we update the start pointer to point the node next to the middle node, i.e., start=mid->next

• If mid->valuetarget: then it means that the target lies in the left half of the linked list since its value is lesser than that of the middle node. So, we should search for it in the left half of the list. Thus, we should update the end pointer to point to the node just before the middle node. We have a mid pointer, but we can’t access the node just before it as we don’t have any previous pointer in our node structure. So, we simply update the end pointer as end = mid.

• Repeat the above steps until the search space is exhausted. That is, until the start becomes equal to the end(both pointers pointing to the same node) or the end becomes NULL.

### Dry Run

Let’s say we are given a Linked list sorted in ascending order and target/key element.

Start-> value=10 End->value=25.
Find Middle node-

Since mid->value = 15 and target = 16, so target>mid->value. Update Start as Start=mid->next and continue to find the middle node again.

Start->value=15 and End->value=25.
Let’s find the middle Node-

Since mid->value = 20 and target =16, so target<mid->value. Update End as End=mid and continue to find the middle node again.

Start->value=16 and End->value=20.
Let’s find the middle Node-

Here, mid->value=16 and target = 16. Since target=mid->value, we have found the target element in the linked list. So, print “Target element found,” and the process is terminated.

Let’s see the code implementation and the analysis of time and space complexity in the next section.

### C++ Implementation

``````// CPP code to implement binary search
#include<bits/stdc++.h>
using namespace std;

// structure of a node of the linked list
struct Node
{
int data;
struct Node* next;
};

// Creating Node
Node *newNode(int x)
{
struct Node* temp = new Node;
temp->data = x;
temp->next = NULL;
return temp;
}

// function to find the middle node of the linked list
struct Node* middle(Node* start, Node* last)
{
// if list is empty
if (start == NULL) return NULL;

// defining two pointers: slow and fast
struct Node *slow = start;
struct Node *fast = start;

while(fast->next != last && fast->next->next != last){
fast = fast->next->next;
slow = slow->next;
}

// slow points to the mid of the linked list
return slow;
}

// Implementing the Binary Search
struct Node* binarySearch(Node *listHead, int target)
{
struct Node* last = NULL;

while(last != start) {
// Find middle
Node* mid = middle(start, last);

// If middle is empty
if (mid == NULL) return NULL;

// If target is present at middle
if (mid -> data == target) return mid;

// If target is more than mid
else if (mid -> data < target) start = mid -> next;

// If the target is less than mid.
else last = mid;
}

// target not present
return NULL;
}

int main()
{
int target = 16;
cout << "Target element:" << target << " not present in the linked list\n";
else
cout << "Target element:" << target << " present in the linked list\n";
return 0;
}
``````

### Java Implementation

``````import java.util.*;

// structure of a node of the linked list
class Node {
int data;
Node next;
Node(int data) {
this.data = data;
this.next = null;
}
}

public class Main {
// function to create a new node
public static Node newNode(int x) {
Node temp = new Node(x);
return temp;
}

// function to find the middle node of the linked list
public static Node middle(Node start, Node last) {
// if list is empty
if (start == null) return null;

// defining two pointers: slow and fast
Node slow = start;
Node fast = start;

while (fast.next != last && fast.next.next != last) {
fast = fast.next.next;
slow = slow.next;
}

// slow points to the mid of the linked list
return slow;
}

// Implementing the Binary Search
public static Node binarySearch(Node listHead, int target) {
Node last = null;

while (last != start) {
// Find middle
Node mid = middle(start, last);

// If middle is empty
if (mid == null) return null;

// If target is present at middle
if (mid.data == target) return mid;

// If target is more than mid
else if (mid.data < target) start = mid.next;

// If the target is less than mid.
else last = mid;
}

// target not present
return null;
}

public static void main(String[] args) {
int target = 16;
System.out.println("Target element: " + target + " not present in the linked list");
else
System.out.println("Target element: " + target + " present in the linked list");
}
}
``````

### Python Implementation

``````# Python code to implement binary search on Singly Linked List

# structure of a node of the linked list
class Node:
def __init__(self, data=None, next=None):
self.data = data
self.next = next

# function to create a new node
def new_node(x):
temp = Node(x)
return temp

# function to find the middle node of the linked list
def middle(start, last):
# if list is empty
if start is None:
return None

# defining two pointers: slow and fast
slow = start
fast = start

while fast.next != last and fast.next.next != last:
fast = fast.next.next
slow = slow.next

# slow points to the mid of the linked list
return slow

# Implementing the Binary Search
last = None

while last != start:
# Find middle
mid = middle(start, last)

# If middle is empty
if mid is None:
return None

# If target is present at middle
if mid.data == target:
return mid

# If target is more than mid
elif mid.data < target:
start = mid.next

# If the target is less than mid.
else:
last = mid

# target not present
return None

target = 16
if result is None:
print("Target element:", target, "not present in the linked list")
else:
print("Target element:", target, "present in the linked list")
``````

### Time Complexity

The time complexity of the above-stated code is O(n), where n is the number of elements in the linked list. Since it takes time proportional to n/2 to find the middle node in a linked list. So, the recurrence relation for the binary search on the linked list becomes -

T(n) = T(n/2) + O(n).

According to Case-3 of the Master’s Theorem for analysis of algorithms, the time complexity will be O(n).

### Space Complexity

The space complexity is O(1), as no extra space is used in this algorithm.

A linked list is a data structure consisting of a sequence of elements, each containing a reference to the next element in the sequence. The elements are called nodes, and the reference is called a pointer.

### What is binary search?

Binary search is an algorithm for efficiently finding an item in a sorted list by repeatedly dividing the search interval in half and checking the middle element.

### What is the time complexity of performing a binary search on linked lists?

The time complexity of performing a binary search on a linked list is O(n).

### What is the space complexity of performing a binary search on linked lists?

The space complexity of performing a binary search on linked lists is O(1).

### Why is a binary search on arrays better than linked lists?

Binary search on arrays is better than binary search on linked lists because on arrays, the time complexity is O(logn), and in linked lists, it is O(n). This is because, in a linked list, elements are not stored in contiguous memory locations.

## Conclusion

In this article, we learned the application of binary search on linked lists. We learned about the intuition and approach for this algorithm. We also learned about its implementation in popular programming languages and their complexity analysis.

For placement preparations, you must look at the problemsinterview experiences, and interview bundles. Enrol in our courses and refer to the mock tests and problems available; look at the Problem Sheets interview experiences, and interview bundle for placement preparations. You can also book an interview session with us.

Consider our paid courses, however, to give your career a competitive advantage!

Happy Coding!

Guided path
Free
Data structures & algorithms (Beginner to Intermediate)
13 chapters
109+ Problems