Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> C++

C++ में सिंगली लिंक्ड लिस्ट पर बाइनरी सर्च


एक सिंगली लिंक्ड लिस्ट एक लिंक्ड लिस्ट होती है (एक डेटा संरचना जो एक नोड का मान और अगले नोड का मेमोरी स्थान संग्रहीत करती है) जो केवल एक दिशा में जा सकती है।

बाइनरी सर्च एक खोज एल्गोरिदम है जो "विभाजन और विजय" सिद्धांत पर आधारित है। यह संरचना के मध्य तत्व को ढूंढता है, उसकी तुलना करता है और असमानता के लिए उसी एल्गोरिदम को पुनरावर्ती रूप से कॉल करता है।

यहां हमें एक सिंगली लिंक्ड लिस्ट और एक तत्व दिया गया है जिसे बाइनरी सर्च का उपयोग करके ढूंढना है।

चूंकि सिंगली लिंक्ड लिस्ट एक ऐसी डेटा संरचना है जो केवल एक पॉइंटर का उपयोग करती है, इसलिए इसका मध्य तत्व ढूंढना आसान नहीं है। सिंगली लिंक्ड लिस्ट के मध्य को खोजने के लिए हम टू-पॉइंटर दृष्टिकोण का उपयोग करते हैं।

एल्गोरिदम

चरण 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
  1. C++ में बाइनरी ट्री को लिंक्ड लिस्ट में फ्लैट करना C++ में बाइनरी ट्री को लिंक्ड लिस्ट में फ्लैट करना

    मान लीजिए हमारे पास एक बाइनरी ट्री है। हमें इसे स्थानांतरित (in-place) करके लिंक्ड लिस्ट में बदलना है (दायाँ पॉइंटर अगले नोड को इंगित करे, बायाँ पॉइंटर null हो)। उदाहरण: ट्री [1,2,5,3,4] → फ्लैट लिस्ट: 1→2→3→4→5 (प्रीऑर्डर ट्रैवर्सल क्रम)। रिवर्स प्रीऑर्डर ट्रैवर्सल ग्लोबल prev = null रखें। रिकर

  1. C++ में बाइनरी सर्च ट्री इटरेटर C++ में बाइनरी सर्च ट्री इटरेटर

    मान लीजिए हम बाइनरी ट्री के लिए एक इटरेटर बनाना चाहते हैं। दो मेथड होंगे। अगला एलिमेंट लौटाने के लिए next() मेथड, और बूलियन मान लौटाने के लिए hasNext() मेथड, जो इंगित करेगा कि अगला एलिमेंट मौजूद है या नहीं। तो यदि ट्री इस तरह है −और फंक्शन कॉल्स का अनुक्रम [next(), next(), hasNext(), next(), h

  1. C++ में बाइनरी खोज प्रोग्राम C++ में बाइनरी खोज प्रोग्राम

    बाइनरी खोज क्या है? बाइनरी खोज (आधा-अंतराल खोज) एक खोज एल्गोरिदम है जो क्रमबद्ध सरणी में लक्ष्य मान की स्थिति ढूंढता है। यह लक्ष्य मान की तुलना मध्य तत्व से करता है और खोज स्थान को आधा कर देता है। मुख्य बिंदु केवल क्रमबद्ध सरणी पर काम करता है समय जटिलता: O(log n) दुनिया के सभी नाम क्रमबद्ध हों तो