Linked List: Perform binary search on a singly linked list

Below are the steps to perform binary search:
Note: Binary search is possible if the list is sorted ascending order.

Step 1: Head node and the key will be provided
Step 2: Find the middle element, using fast and slow pointer approach.
Step 3: If the middle element and the key are same, then return.
Step 4: Else if the middle element < key, then move to the upper half
Step 5: Else if the middle element > key, then move to the lower half
Step 6: We terminate the loop, if “last->next == start”, if no value matches the key value.

This approach will take O(n) time.

Solution in C++

#include<iostream>
#include<vector>
#include<string>

using namespace std;

struct Node
{
	int data;
	Node *next;

	Node(int x)
	{
		data = x;
		next = NULL;
	}
};


void print_list(Node *head)
{
	Node *start = head;

	while(start)
	{
		cout<<start -> data<< " -> ";
		start = start->next;
	}
	cout<<endl;
}

Node* get_middle(Node* head, Node* last)
{
	if(head == NULL)
		return NULL;

	Node* slow = head;
	Node* fast = head -> next;

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

	return slow;
}

Node* perform_binay_search(Node *head, int key)
{
	Node* start = head;
	Node* last = NULL;

	do
	{
		Node *mid = get_middle(start, last);

		if(mid == NULL)
			return NULL;

		if(mid->data == key)
			return mid;

		if(mid-> data < key)
			start = mid -> next; 
  
          else
            last = mid; 

	}while(last == NULL || last->next == start);

	return NULL;
}

int main()
{
	Node *head =  new Node(1);
	head -> next =  new Node(2);
	head -> next -> next =  new Node(3);
	head -> next -> next -> next =  new Node(4);
	head -> next -> next -> next -> next =  new Node(5);
	head -> next -> next -> next -> next -> next=  new Node(6);

	int key = 6;

	cout<<"The given list \n";
	print_list(head);

	if (perform_binay_search(head, key) == NULL)
		cout<<"\nThe key "<<key<<" is not present"<<endl;
	else
		cout<<"\nThe key "<<key<<" is present"<<endl;

	return 0;
}

Output:

The given list
1 -> 2 -> 3 -> 4 -> 5 -> 6 ->

The key 6 is present