সিঙ্গলি লিংকড লিস্টে বাইনারি সার্চ C++-এ

সিঙ্গলি লিংকড লিস্ট হল একটি লিংকড লিস্ট (একটি ডেটা স্ট্রাকচার যা একটি নোডের মান এবং পরবর্তী নোডের মেমরি লোকেশন সংরক্ষণ করে) যা শুধুমাত্র একদিকে যেতে পারে।

বাইনারি সার্চ হল ভাগ করো এবং শাসন করো (divide and conquer) পদ্ধতিতে ভিত্তিক একটি সার্চ অ্যালগরিদম। এটি স্ট্রাকচারের মাঝপথের উপাদান খুঁজে বের করে এবং তা তুলনা করে, অসমানতা থাকলে একই অ্যালগরিদমকে রিকার্সিভভাবে কল করে।

এখানে একটি সিঙ্গলি লিংকড লিস্ট এবং একটি উপাদান দেওয়া আছে যা বাইনারি সার্চ ব্যবহার করে খুঁজে বের করতে হবে।

যেহেতু সিঙ্গলি লিংকড লিস্ট একটি পয়েন্টার ব্যবহার করে, এর মাঝপথের উপাদান খুঁজে বের করা সহজ নয়। সিঙ্গলি লিংকড লিস্টের মাঝপথ খুঁজে বের করতে টু-পয়েন্টার পদ্ধতি ব্যবহার করা হয়।

অ্যালগরিদম

ধাপ ১: start_node (লিস্টের হেড), last_node (শেষ মান রাখবে), mid_node (স্ট্রাকচারের মাঝপথের নোড) আরম্ভ করুন।
ধাপ ২: mid_node কে উপাদানের সাথে তুলনা করুন
  ধাপ ২.১: যদি mid_node = উপাদান হয়, "found" রিটার্ন করুন।
  ধাপ ২.২: যদি mid_node > উপাদান হয়, নিম্নের আধার অংশে বাইনারি সার্চ কল করুন।
  ধাপ ২.৩: যদি mid_node < উপাদান হয়, উপরের আধার অংশে বাইনারি সার্চ কল করুন।
ধাপ ৩: যদি পুরো লিস্ট ট্রভার্স হয়ে যায়, "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