Binary search on Linked List

Introduction

In this article, we will learn how to perform a binary search on linked list in an effective way. Binary Search is a searching algorithm which is performed on the sorted elements in which element is searched in the middle portion of the linked list. We already know binary search will be used on sorted data. So let’s understand how can we perform a binary search on linked list.

Problem Statement

In this problem, we are given a sorted Singly Linked List and an integer X, and we need to find and tell if the list contains a given element X or not.

Problem Statement Understanding

Let’s learn programming languages online and try to understand the problem statement with the help of examples.

If the given linked list is

  • According to the problem statement, the given linked list is sorted, and we need to tell if the list contains element X or not.
  • If element X is present we will print Element Found else we print Element not Found.
  • We can see that X = 5 is present in the linked list, so we will print ‘Element Found’.

If the given sorted linked list is head→1→3→5→7→9→NULL and X=8.

  • So we can see that X = 8 is not present in the given linked list, so we will print Element not Found.

Now I think from the above examples, the problem is clear. So let’s see how we can approach it.

A straightforward way to check if an element X is present in the linked list is to traverse the linked list and check if for any node (node→data == X):

  • If node→data == X, it will mean that element X is present in the linked list.
  • Otherwise, if none of the node’s data is equal to X during the whole traversal, it will mean that element X is not present in the linked list.

Although the above linear traversal to check if any element X is present in the linked list or not will work fine, but here we are asked to use Binary search.

So let’s see how we can use binary search to check if an element X is present in a linked list or not.

Approach of binary search on linked list

Here we will see how we can use binary search algorithm to check whether a certain element X is present in the given list or not.

Initially, the range of binary search will be the complete list, i.e., from head to the last node of the list. Binary search first compares the target element X with the middle element based on which it reduces the range for further search.

  • If the middle element is equal to the target element X, then we have found our element.
  • Else, if the target element X is less than the middle element, then the range of binary search will reduce, and our new range will be from start to middle element of the linked list.
  • Else, If the target element X is greater than the middle element, the search range will reduce and our new search range will be from middle→next to the end of the list.

The searching will go on until one of the following condition hits:

  • We find element X.
  • The search range collapses, and we don’t have any element in the search range to check.

The time complexity of binary search on linked list is O(log n) which is much better than linear search which takes linear time O(n) to search an element, but for binary to work properly the given must be sorted. Its time complexity is less than O(n) because it does not check every element of the given list. The search reduces to half at every iteration.

Let’s see the algorithm.

Algorithm to perform binary search in linked list

To find an element X in the singly linked list, we need to find the middle of the list and then divide the list into 2 halves and perform the operations on the favorable part of the list and repeat the above steps until we find the required key in the list.

  • First, we need to find the middle node of the linked list, which we will find using the slow and fast pointer method.
    • In slow and fast pointer method, we will run a while loop until the fast pointer or next of the fast pointer hits null and in each iteration, we will move fast by 2 nodes at a time (fast = fast→next→next) and slow one node at a time ( slow=slow→next).
    • So when the pointers exit the while loop, the slow pointer will be pointing to the middle node of the linked list.
  • Then, after finding the middle node of the list, we need to compare the value of the middle node of the list with the target element X.
    • If the middle node value of the list is equal to target element X, so we return middle as the answer.
    • If the middle node value is less than the target element X, we update the start pointer with middle→next.
    • If the middle node value is greater than the element X, we update the last pointer to the middle node.
  • We perform the above operations until the start node equals last node or the last node becomes NULL.
  • Then we check if the node returned by the function is not NULL we print Element Found else we print Element not Found.

Dry Run

Code Implementation:

#include<stdio.h>
#include<stdlib.h>
 
struct Node
{
    int data;
    struct Node* next;
};
 
struct Node *newNode(int x)
{
    struct Node* temp = (struct Node*)malloc(sizeof(struct Node));
    temp->data = x;
    temp->next = NULL;
    return temp;
}
 
// function to find out middle element
struct Node* middle(struct Node* start,struct Node* last)
{
    if (start == NULL)
        return NULL;
 
    struct Node* slow = start;
    struct Node* fast = start -> next;
 
    while (fast != last)
    {
        fast = fast -> next;
        if (fast != last)
        {
            slow = slow -> next;
            fast = fast -> next;
        }
    }
 
    return slow;
}
 
// Function for implementing the Binary
// Search on linked list
struct Node* binarySearch(struct Node *head, int value)
{
    struct Node* start = head;
    struct Node* last = NULL;
 
    do
    {
        // Find middle
        struct Node* mid = middle(start, last);
 
        // If middle is empty
        if (mid == NULL)
            return NULL;
 
        // If value is present at middle
        if (mid -> data == value)
            return mid;
 
        // If value is more than mid
        else if (mid -> data < value)
            start = mid -> next;
 
        // If the value is less than mid.
        else
            last = mid;
 
    } while (last == NULL ||
             last != start);
 
    // value not present
    return NULL;
}
 
// Driver Code
int main()
{
    struct Node *head = newNode(1);
    head->next = newNode(4);
    head->next->next = newNode(7);
    head->next->next->next = newNode(8);
    head->next->next->next->next = newNode(9);
    head->next->next->next->next->next = newNode(10);
    int value = 8;
    if (binarySearch(head, value) == NULL)
        printf("Value not present\n");
    else
        printf("Present");
    return 0;
}
#include<bits stdc++.h="">
using namespace std;
 
struct Node
{
    int data;
    struct Node* next;
};
 
Node *newNode(int x)
{
    struct Node* temp = new Node;
    temp->data = x;
    temp->next = NULL;
    return temp;
}

struct Node* find_middle_node(Node* start, Node* last)
{
    if (start == NULL){
        return NULL;
    }
 
    struct Node* slow = start;
    struct Node* fast = start -> next;
 
    while (fast != last)
    {
        fast = fast -> next;
        if (fast != last)
        {
            slow = slow -> next;
            fast = fast -> next;
        }
    }
 
    return slow;
}
 

struct Node* binarySearch(Node *head, int value){
    struct Node* start = head;
    struct Node* last = NULL;
 
    do
    {
        Node* mid = find_middle_node(start, last);

        if (mid == NULL){
            return NULL;
        }
 
        if (mid -> data == value){
            return mid;
        }
 
        else if (mid -> data < value){
            start = mid -> next;
        }
        
        else{
            last = mid;
        }
 
    } while (last == NULL ||
             last != start);
 
    return NULL;
}
 

int main()
{
    Node *head = newNode(2);
    head->next = newNode(5);
    head->next->next = newNode(7);
    head->next->next->next = newNode(11);
    head->next->next->next->next = newNode(15);
    head->next->next->next->next->next = newNode(18);
    int value = 5;
    if (binarySearch(head, value) == NULL)
        printf("Element not Found\n");
    else
        printf("Element Found");
    return 0;
}
class Node
{
    int data;
    Node next;

    Node(int d)
    {
        data = d;
        next = null;
    }
}
 
class BinarySearch
{
    static Node push(Node head, int data)
    {
        Node newNode = new Node(data);
        newNode.next = head;
        head = newNode;
        return head;
    }
    static Node middleNode(Node start, Node last)
    {
        if (start == null)
            return null;
 
        Node slow = start;
        Node fast = start.next;
 
        while (fast != last)
        {
            fast = fast.next;
            if (fast != last)
            {
                slow = slow.next;
                fast = fast.next;
            }
        }
        return slow;
    }
    static Node binarySearch(Node head, int value)
    {
        Node start = head;
        Node last = null;
 
        do
        {
           
            Node mid = middleNode(start, last);
 
           
            if (mid == null)
                return null;
 
            if (mid.data == value)
                return mid;
 
            else if (mid.data > value)
            {
                start = mid.next;
            }
            else
                last = mid;
        } while (last == null || last != start);
 
        return null;
    }
    public static void main(String[] args)
    {
        Node head = null;
 
        head = push(head, 2);
        head = push(head, 5);
        head = push(head, 7);
        head = push(head, 11);
        head = push(head, 15);
        head = push(head, 18);
        int value = 7;
 
        if (binarySearch(head, value) == null)
        {
            System.out.println("Element not found");
        }
        else
        {
            System.out.println("Element found");
        }
    }
}
class Node:
    
    def __init__(self, data):
        self.data = data
        self.next = None
        self.prev = None
        
def newNode(x):

    temp = Node(0)
    temp.data = x
    temp.next = None
    return temp

def middle(start, last):

    if (start == None):
        return None

    slow = start
    fast = start . next

    while (fast != last):
    
        fast = fast . next
        if (fast != last):
        
            slow = slow . next
            fast = fast . next
        
    return slow

def binarySearch(head,value):

    start = head
    last = None

    while True :
    
        mid = middle(start, last)

        if (mid == None):
            return None

        if (mid . data == value):
            return mid

        elif (mid . data < value):
            start = mid . next

        else:
            last = mid

        if not (last == None or last != start):
            break

    return None

head = newNode(2)
head.next = newNode(5)
head.next.next = newNode(7)
head.next.next.next = newNode(11)
head.next.next.next.next = newNode(15)
head.next.next.next.next.next = newNode(18)
value = 9
if (binarySearch(head, value) == None):
    print("Element not Found\n")
else:
    print("Element Found")

Output

Element Found

Time Complexity: O(n), where n is the total number of nodes in the Singly Linked List though we are performing a Binary search still in the worst case the complexity is O(n).

Conclusion

In this blog, we learned to perform a binary search on linked list. Our experts continuously try to give you a better choice of questions, you can follow the link and masters in the linked list. We hope you will understand how to apply binary search on linked list.

FAQs

  1. Can we do a binary search on linked list?
  2. Yes, binary search is possible on linked lists if the linked list is in an ordered format and we know the count of the nodes in the linked list.

  3. Which search is best for the linked list?
  4. You have two choices for applying search algorithms on linked lists:

    • Linear search on unordered lists. Which takes O(N).
    • Binary search is possible by using a skip list.
  5. Why is binary search faster than linear search?
  6. Binary search is faster than linear search when the given array is already sorted.

Leave a Reply

Your email address will not be published. Required fields are marked *