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