एक एकल लिंक की गई सूची एक लिंक की गई सूची है (एक डेटा संरचना जो एक नोड के मूल्य और अगले नोड के मेमोरी स्थान को संग्रहीत करती है) जो केवल एक ही तरफ जा सकती है।
एक द्विआधारी खोज डिवाइड एंड रूल पर आधारित एक सर्च एल्गोरिथम है। यह संरचना के मध्य तत्व को ढूंढता है और असमानता के लिए समान एल्गोरिदम के लिए पुनरावर्ती कॉल की तुलना और उपयोग करता है।
यहां, हमें एक एकल लिंक की गई सूची और एक द्विआधारी खोज का उपयोग करके पाया जाने वाला एक तत्व दिया गया है।
चूंकि सिंगल लिंक्ड लिस्ट एक डेटा संरचना है जो केवल एक पॉइंटर का उपयोग करती है, इसके मध्य तत्व को खोजना आसान नहीं है। सिंगल लिंक्ड लिस्ट के मध्य में, हम दो पॉइंटर एप्रोच का उपयोग करते हैं।
एल्गोरिदम
Step 1 : Initialize, start_node (head of list) and last_node (will have last value) , mid_node (middle node of the structure). Step 2 : Compare mid_node to element Step 2.1 : if mid_node = element, return value “found”. Step 2.2 : if mid_node > element, call binary search on lower_Half. Step 2.3 : if mid_node < element, call binary search on upper_Half. Step 3 : if entire list is traversed, return “Not found”.
उदाहरण
#include<stdio.h>
#include<stdlib.h>
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* mid_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 = mid_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(54);
head->next = newNode(12);
head->next->next = newNode(18);
head->next->next->next = newNode(23);
head->next->next->next->next = newNode(52);
head->next->next->next->next->next = newNode(76);
int value = 52;
if (binarySearch(head, value) == NULL)
printf("Value is not present in linked list\n");
else
printf("The value is present in linked list\n");
return 0;
} आउटपुट
The value is present in linked list