การค้นหาแบบทวิภาคบนรายการเชื่อมโยงเดี่ยวใน C++

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

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

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

เนื่องจากรายการเชื่อมโยงเดี่ยวใช้เพียงตัวชี้ (pointer) เดียว การหาองค์ประกอบตรงกลางจึงไม่สะดวก เราจึงใช้วิธีการสองตัวชี้ (two-pointer approach) เพื่อหาตำแหน่งกลางของรายการเชื่อมโยงเดี่ยว

อัลกอริทึม

ขั้นตอน 1: เริ่มต้น start_node (หัวของรายการ) และ last_node (จะมีค่าสุดท้าย), mid_node (โหนดตรงกลางของโครงสร้าง)
ขั้นตอน 2: เปรียบเทียบ mid_node กับองค์ประกอบที่ต้องการ
  ขั้นตอน 2.1: ถ้า mid_node = องค์ประกอบ ให้คืนค่า "พบ"
  ขั้นตอน 2.2: ถ้า mid_node > องค์ประกอบ ให้เรียก binary search บนครึ่งล่าง
  ขั้นตอน 2.3: ถ้า mid_node < องค์ประกอบ ให้เรียก binary search บนครึ่งบน
ขั้นตอน 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