Problem Statement: You are given a sorted singly linked list and a key (element to be searched), find the key in the linked list using binary search algorithm. The challenge is to find the middle element as Linked List does not support random access.

Binary search is used because it has a time complexity of O(N) for a sorted array.

If we follow sequential access of Linked List, then it will take O(N) time to find the middle element. With this, the overall time complexity of Binary Search on Linked List will become O(N * logN).

This will slower than linear search.

The trick is to find the middle element using two pointer approach using which the time complexity will be O(N) for Binary Search on Linked List. With Skip List which is a modification of Linked List, we can achieve O(logN) time complexity for Binary Search.

Hence, the main points are as follows:

• Binary Search: O(logN) for array
• Binary Search: O(N) for Singly Linked List
• Binary Search: O(logN) for Skip List

Sample Testcase to understand the problem:

Linked List : 1->3->5->8->9->10->11->13->NULL
Input : Enter value to search : 10
Output : Found

Input : Enter value to search : 12
Output : Not Found

Explanation of using Binary Search

To perform a Binary Search Algorithm on Singly Linked Lists, determination of the middle element is important. Binary Search is fast and efficient because accessing the middle elemen is fast. In arrays, binary search takes O(1) time to access middle element. But memory allocation for the singly linked list is non-contiguous, which makes finding the middle element difficult and time consuming.

The node structure for Linked List is as follows:

// Node structure
struct Node 
{ 
    int data; 
    Node* next; 
};

Finding middle element: Two pointer approach

1. Traverse the singly linked list using two pointers.
2. Move one pointer by one step ahead and the other pointer by two steps.
3. When the fast pointer reaches the end of the singly linked list, the slow pointer will reach the middle of the singly linked list.
4. Return slow pointer address.

Code

// function to find out middle element 
Node* middle(Node* start, Node* last) 
{ 
    // if start points to NULL and is empty
    if (start == NULL) 
        return NULL; 
  
    Node* slow = start; 
    Node* fast = start -> next; 
  
    while (fast != last) 
    { 
        // fast is moved one step ahead
        fast = fast -> next; 
        // if fast is not the last element
        if (fast != last)
        { 
            // slow pointer is moved one step ahead
            slow = slow -> next; 
            // fast pointer is moved second step ahead
            fast = fast -> next; 
        } 
    } 
  
    return slow; 
} 

BINARY SEARCH ALGORITHM

Pseudo Code Algorithm

1. Start node is set to head of the list and the last node is set to NULL.
2. Middle element is calculated using the two pointers approach discussed above.
3. If the middle element is same as the key to be searched, we return it.
4. Else if middle element is less than the key to be searched, we have to search is the right side of the singly linked list. So, we set start pointer to the next of middle element.
5. Else if middle element is greater than the key to be searched, we have to search is the left side of the singly linked list. So, we set last pointer to the middle element.
6. If the key is found or the entire linked list gets traversed once, we break the loop.

Code

// Node structure
struct Node 
{ 
    int data; 
    Node* next; 
}; 

// function to find out middle element 
Node* middle(Node* start, Node* last) 
{ 
    // if start points to NULL and is empty
    if (start == NULL) 
        return NULL; 
  
    Node* slow = start; 
    Node* fast = start -> next; 
  
    while (fast != last) 
    { 
        // fast is moved one step ahead
        fast = fast -> next; 
        // if fast is not the last element
        if (fast != last)
        { 
            // slow pointer is moved one step ahead
            slow = slow -> next; 
            // fast pointer is moved second step ahead
            fast = fast -> next; 
        } 
    } 
  
    return slow; 
} 

// Function for implementing the Binary Search on Singly Linked List
Node* binarySearch(Node *head, int key) 
{ 
    Node* start = head; 
    Node* last = NULL; 
    
    do
    { 
        // calling middle function to find middle element
        Node* mid = middle(start, last); 
  
        // If middle element is empty 
        if (mid == NULL) 
            return NULL; 
  
        // If value is present at middle, we return it
        if (mid -> data == key) 
            return mid; 
  
        // If value is more than mid 
        else if (mid -> data < key) 
            start = mid -> next; 
  
        // If the value is less than mid. 
        else
            last = mid; 
  
    } while (last == NULL || last != start); 
  
    // value not present, so we return NULL
    return NULL; 
} 

Complexity Analysis

We'll look at the asymptotic complexity of our solution which comes to be O(N) as we are traversing the singly linked list at least once either to find the middle element or to move the pointers for binary search.