একটি এককভাবে লিঙ্ক করা তালিকা৷ এটি একটি লিঙ্কযুক্ত তালিকা (একটি ডেটা কাঠামো যা একটি নোডের মান এবং পরবর্তী নোডের মেমরি অবস্থান সংরক্ষণ করে) যা শুধুমাত্র একটি উপায়ে যেতে পারে৷
একটি বাইনারি অনুসন্ধান ভাগ এবং নিয়মের উপর ভিত্তি করে একটি অনুসন্ধান অ্যালগরিদম। এটি কাঠামোর মধ্যম উপাদান খুঁজে পায় এবং অসমতার জন্য একই অ্যালগরিদমের সাথে পুনরাবৃত্তিমূলক কলগুলির তুলনা করে এবং ব্যবহার করে৷
এখানে, আমাদেরকে একটি এককভাবে লিঙ্ক করা তালিকা দেওয়া হয়েছে এবং একটি উপাদান বাইনারি অনুসন্ধান ব্যবহার করে পাওয়া যাবে।
যেহেতু এককভাবে লিঙ্ক করা তালিকাটি একটি ডেটা স্ট্রাকচার যা শুধুমাত্র একটি পয়েন্টার ব্যবহার করে, এটির মাঝের উপাদানটি খুঁজে পাওয়া সহজ নয়৷ এককভাবে সংযুক্ত তালিকার মাঝখানে, আমরা দুটি পয়েন্টার পদ্ধতি ব্যবহার করি।
অ্যালগোরিদম
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
