C++의 단일 연결 목록에 대한 이진 검색

단일 연결 목록 한 방향으로만 갈 수 있는 연결 리스트(노드의 값과 다음 노드의 메모리 위치를 저장하는 데이터 구조)입니다.

바이너리 검색 분할 규칙에 기반한 검색 알고리즘입니다. 이는 구조의 중간 요소를 찾고 부등식에 대해 동일한 알고리즘에 대한 재귀 호출을 비교하고 사용합니다.

여기에 단일 연결 목록과 이진 검색을 사용하여 찾을 요소가 제공됩니다.

단일 연결 리스트는 포인터를 하나만 사용하는 데이터 구조이기 때문에 중간 요소를 찾기가 쉽지 않습니다. 단일 연결 목록의 중간에 두 가지 포인터 접근 방식을 사용합니다.

알고리즘

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