Trong lĩnh vực cấu trúc dữ liệu, tìm kiếm là một thao tác cơ bản và thiết yếu. Các thuật toán tìm kiếm nội (thực hiện hoàn toàn trong bộ nhớ) đóng vai trò then chốt trong việc tối ưu hiệu suất truy xuất dữ liệu. Dưới đây là ba phương pháp tiêu biểu: tìm kiếm tuần tự, tìm kiếm theo khối và tìm kiếm nhị phân.

Tìm kiếm tuần tự

Đây là kỹ thuật đơn giản nhất, duyệt từng phần tử từ đầu đến cuối mảng để so sánh với giá trị cần tìm. Nếu tìm thấy, trả về vị trí; nếu không, thông báo thất bại.

Độ phức tạp thời gian: O(n)

#include <stdio.h>

int linearFind(int arr[], int len, int key) {
    for (int idx = 0; idx < len; idx++) {
        if (arr[idx] == key) return idx;
    }
    return -1;
}

int main() {
    int dataset[] = {15, 22, 8, 37, 41, 6, 19};
    int size = sizeof(dataset) / sizeof(dataset[0]);
    int searchVal = 37;

    int result = linearFind(dataset, size, searchVal);
    if (result == -1) {
        printf("Không tìm thấy giá trị %d trong mảng.\n", searchVal);
    } else {
        printf("Tìm thấy %d tại vị trí thứ %d (tính từ 1).\n", searchVal, result + 1);
    }
    return 0;
}

Tìm kiếm theo khối

Chia mảng thành các khối con, mỗi khối có kích thước cố định. Mỗi khối được đặc trưng bởi giá trị lớn nhất trong khối đó. Bảng chỉ mục chứa các giá trị cực đại này, giúp xác định nhanh khối chứa giá trị cần tìm, sau đó thực hiện tìm kiếm tuyến tính trong khối đó.

Độ phức tạp: giữa O(n) và O(log n)

#include <stdio.h>

#define CHUNK_SIZE 4

typedef struct {
    int items[CHUNK_SIZE];
    int peak;
} Segment;

int chunkedSearch(Segment segments[], int segCount, int value) {
    int blockIdx = 0;
    while (blockIdx < segCount && segments[blockIdx].peak < value) {
        blockIdx++;
    }

    if (blockIdx >= segCount) return -1;

    for (int localIdx = 0; localIdx < CHUNK_SIZE; localIdx++) {
        if (segments[blockIdx].items[localIdx] == value) {
            return blockIdx * CHUNK_SIZE + localIdx;
        }
    }
    return -1;
}

int main() {
    Segment groups[] = {
        {{10, 14, 12, 11}, 14},
        {{20, 25, 23, 21}, 25},
        {{30, 33, 31, 32}, 33}
    };
    int totalBlocks = sizeof(groups) / sizeof(groups[0]);
    int query = 23;

    int pos = chunkedSearch(groups, totalBlocks, query);
    if (pos == -1) {
        printf("Giá trị %d không tồn tại.\n", query);
    } else {
        printf("Tìm thấy %d tại vị trí %d.\n", query, pos + 1);
    }
    return 0;
}

Tìm kiếm nhị phân

Yêu cầu mảng đã được sắp xếp. Thuật toán liên tục chia đôi phạm vi tìm kiếm: so sánh giá trị giữa với khóa tìm kiếm, sau đó thu hẹp phạm vi sang nửa trái hoặc phải tùy theo kết quả so sánh.

Độ phức tạp thời gian: O(log n)

#include <stdio.h>

void binaryLocate(int sortedArr[], int length, int key) {
    int start = 0, end = length - 1;

    while (start <= end) {
        int center = (start + end) / 2;
        if (sortedArr[center] == key) {
            printf("Tìm thấy %d tại vị trí %d.\n", key, center + 1);
            return;
        } else if (sortedArr[center] < key) {
            start = center + 1;
        } else {
            end = center - 1;
        }
    }
    printf("Không tìm thấy giá trị %d.\n", key);
}

int main() {
    int orderedData[] = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};
    int count = sizeof(orderedData) / sizeof(orderedData[0]);
    int target = 23;

    binaryLocate(orderedData, count, target);
    return 0;
}