Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
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.
Frequently Asked Questions
5.1.
What are linked lists?
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

Author Shubham Agarwal
3 upvotes
gp-icon
Data structures & algorithms (Beginner to Intermediate)
Free guided path
13 chapters
99+ problems
gp-badge
Earn badges and level up

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. 

Introduction

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.

Also read - Merge sort in linked list

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.

Input

Linked List: 10->12->15->16->20->NULL

Target = 16

Output

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.

 

Linked list example

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

Step 1

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-

Step 2

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-

Step 3

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
// on Singly Linked List
#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* start = listHead;
    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()
{
    Node *listHead = newNode(10);
    listHead->next = newNode(12);
    listHead->next->next = newNode(15);
    listHead->next->next->next = newNode(16);
    listHead->next->next->next->next = newNode(20);
    listHead->next->next->next->next->next = newNode(25);
    int target = 16;
    if (binarySearch(listHead, target) == NULL)
        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 start = listHead;
        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) {
        Node listHead = newNode(10);
        listHead.next = newNode(12);
        listHead.next.next = newNode(15);
        listHead.next.next.next = newNode(16);
        listHead.next.next.next.next = newNode(20);
        listHead.next.next.next.next.next = newNode(25);
        int target = 16;
        if (binarySearch(listHead, target) == null)
            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
def binary_search(list_head, target):
    start = list_head
    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

list_head = new_node(10)
list_head.next = new_node(12)
list_head.next.next = new_node(15)
list_head.next.next.next = new_node(16)
list_head.next.next.next.next = new_node(20)
list_head.next.next.next.next.next = new_node(25)
target = 16
result = binary_search(list_head, target)
if result is None:
    print("Target element:", target, "not present in the linked list")
else:
    print("Target element:", target, "present in the linked list")

Output

Output

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.

Frequently Asked Questions

What are linked lists?

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. 

Check out our articles if you think this blog has helped you enhance your knowledge and want to learn more. Visit our website to read more such blogs. 

  1. Introduction To Binary Search Algorithm 
  2. Searching and Sorting Algorithms 
  3. Application of Linked List Data Structure 
  4. Operations on Linked Lists in C/C++ 
  5. Finding the Middle Node of a Linked List 
  6. Advantages and Disadvantages of Linked List
  7.  Difference Between Array List and Linked List
  8. Doubly Linked List

 

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
gridgp-icon
Data structures & algorithms (Beginner to Intermediate)
13 chapters
109+ Problems
gp-badge
Earn badges and level up
Live masterclass