एक सिंगली लिंक्ड लिस्ट एक लिंक्ड लिस्ट होती है (एक डेटा संरचना जो एक नोड का मान और अगले नोड का मेमोरी स्थान संग्रहीत करती है) जो केवल एक दिशा में जा सकती है।
बाइनरी सर्च एक खोज एल्गोरिदम है जो "विभाजन और विजय" सिद्धांत पर आधारित है। यह संरचना के मध्य तत्व को ढूंढता है, उसकी तुलना करता है और असमानता के लिए उसी एल्गोरिदम को पुनरावर्ती रूप से कॉल करता है।
यहां हमें एक सिंगली लिंक्ड लिस्ट और एक तत्व दिया गया है जिसे बाइनरी सर्च का उपयोग करके ढूंढना है।
चूंकि सिंगली लिंक्ड लिस्ट एक ऐसी डेटा संरचना है जो केवल एक पॉइंटर का उपयोग करती है, इसलिए इसका मध्य तत्व ढूंढना आसान नहीं है। सिंगली लिंक्ड लिस्ट के मध्य को खोजने के लिए हम टू-पॉइंटर दृष्टिकोण का उपयोग करते हैं।
एल्गोरिदम
चरण 1: प्रारंभ करें, start_node (लिस्ट का हेड) और last_node (अंतिम मान रखेगा), mid_node (संरचना का मध्य नोड)। चरण 2: mid_node की तुलना तत्व से करें चरण 2.1: यदि mid_node = तत्व, तो "मिला" वापस करें। चरण 2.2: यदि mid_node > तत्व, तो निचले आधे भाग पर बाइनरी सर्च कॉल करें। चरण 2.3: यदि mid_node < तत्व, तो ऊपरी आधे भाग पर बाइनरी सर्च कॉल करें। चरण 3: यदि पूरी लिस्ट पार हो गई है, तो "नहीं मिला" वापस करें।
उदाहरण
#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