การค้นหาแบบไบนารีในรายการที่เชื่อมโยงโดยลำพังใน C ++

A รายการที่เชื่อมโยงเพียงรายการเดียว เป็นรายการที่เชื่อมโยง (โครงสร้างข้อมูลที่จัดเก็บค่าของโหนดและตำแหน่งหน่วยความจำของโหนดถัดไป) ซึ่งสามารถไปได้ทางเดียวเท่านั้น

การค้นหาแบบไบนารี เป็นอัลกอริธึมการค้นหาตามการแบ่งและกฎ ที่ค้นหาองค์ประกอบตรงกลางของโครงสร้างและเปรียบเทียบและใช้การเรียกซ้ำกับอัลกอริทึมเดียวกันสำหรับความไม่เท่าเทียมกัน

ในที่นี้ เราได้รับรายการที่เชื่อมโยงโดยลำพังและองค์ประกอบที่จะพบโดยใช้การค้นหาแบบไบนารี

เนื่องจากรายการที่เชื่อมโยงโดยลำพังเป็นโครงสร้างข้อมูลที่ใช้ตัวชี้เพียงตัวเดียว การค้นหาองค์ประกอบตรงกลางจึงไม่ใช่เรื่องง่าย เราใช้ตัวชี้ 2 วิธีในการอยู่ตรงกลางของรายการลิงก์เดียว

อัลกอริทึม

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