Tìm kiếm nhị phân trên danh sách liên kết đơn trong C++

Danh sách liên kết đơn (singly linked list) là một cấu trúc dữ liệu lưu trữ giá trị của nút và địa chỉ bộ nhớ của nút tiếp theo, chỉ cho phép duyệt theo một chiều.

Tìm kiếm nhị phân (binary search) là thuật toán tìm kiếm dựa trên chiến lược chia để trị. Thuật toán tìm phần tử giữa của cấu trúc, so sánh và sử dụng đệ quy để tìm kiếm trên nửa còn lại nếu không bằng.

Bài toán: Cho một danh sách liên kết đơn và một phần tử cần tìm bằng tìm kiếm nhị phân.

Vì danh sách liên kết đơn chỉ sử dụng một con trỏ, việc tìm phần tử giữa không trực tiếp như mảng. Ta sử dụng kỹ thuật hai con trỏ (two-pointer approach) để tìm nút giữa: con trỏ slow di chuyển một bước, con trỏ fast di chuyển hai bước; khi fast đến cuối, slow sẽ ở giữa.

THUẬT TOÁN

Bước 1: Khởi tạo start_node (đầu danh sách), last_node (giá trị cuối), mid_node (nút giữa).
Bước 2: So sánh mid_node với phần tử cần tìm
    2.1: Nếu mid_node = phần tử → trả về "tìm thấy".
    2.2: Nếu mid_node > phần tử → gọi đệ quy tìm kiếm trên nửa dưới.
    2.3: Nếu mid_node < phần tử → gọi đệ quy tìm kiếm trên nửa trên.
Bước 3: Nếu duyệt hết danh sách mà không thấy → trả về "Không tìm thấy".

Ví dụ minh họa (C++)

#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("Gia tri khong ton tai trong danh sach lien ket\n");
    else
        printf("Gia tri ton tai trong danh sach lien ket\n");
    return 0;
}

Kết quả

Gia tri ton tai trong danh sach lien ket