Các thuật toán tìm kiếm là thành phần thiết yếu trong xử lý dữ liệu, đặc biệt khi làm việc với mảng lớn đã được sắp xếp. Bài viết này trình bày một loạt phép đo thực nghiệm nhằm so sánh bốn phương pháp tìm kiếm phổ biến: tìm nhị phân, tìm tuyến tính, tìm nội suy và tìm nhảy — dựa trên cài đặt tham khảo từ kho mã nguồn gh_mirrors/al/algorithms. Các kết quả được thu thập trên các tập dữ liệu có kích thước khác nhau, giúp xác định rõ ràng ưu điểm và giới hạn thực tế của từng thuật toán.

Môi trường và quy trình thử nghiệm

Các bài kiểm tra được thực hiện trên hệ thống Linux với Python 3.11, CPU Intel Core i5 và 8 GB RAM. Dữ liệu đầu vào là các mảng số nguyên dương tăng dần, được sinh ngẫu nhiên nhưng đảm bảo tính đồng đều (đối với thử nghiệm tìm nội suy) hoặc chỉ yêu cầu tính tuần tự (các thuật toán còn lại).

• Kích thước mảng: 10⁵, 10⁶ và 10⁷ phần tử
• Mỗi thuật toán thực hiện 100 lần tìm kiếm ngẫu nhiên (50% trúng, 50% không trúng)
• Thời gian đo được lấy trung bình theo đơn vị microsecond (µs), sau đó quy đổi sang millisecond (ms) để dễ so sánh

Phân tích cài đặt và đặc điểm lý thuyết

Tìm nhị phân (Binary Search)

Thuật toán chia đôi liên tục khoảng tìm kiếm, yêu cầu mảng phải được sắp xếp. Độ phức tạp thời gian trong mọi trường hợp là O(log n).

def locate_by_bisection(data, key):
    left, right = 0, len(data) - 1
    while left <= right:
        center = left + (right - left) // 2
        if data[center] == key:
            return center
        elif data[center] < key:
            left = center + 1
        else:
            right = center - 1
    return -1

Tìm tuyến tính (Linear Search)

Duyệt tuần tự từ đầu đến cuối mảng. Không cần điều kiện về thứ tự hay phân bố dữ liệu. Độ phức tạp trung bình và xấu nhất là O(n).

def scan_sequentially(data, key):
    for idx, val in enumerate(data):
        if val == key:
            return idx
    return -1

Tìm nội suy (Interpolation Search)

Mở rộng tìm nhị phân bằng cách ước lượng vị trí mục tiêu dựa trên giá trị đầu – cuối và phân bố tuyến tính. Hiệu quả cao nhất khi dữ liệu phân bố đều. Độ phức tạp trung bình: O(log log n); tệ nhất: O(n).

def estimate_position(data, key, lo, hi):
    if lo >= hi or key < data[lo] or key > data[hi]:
        return -1
    pos = lo + int((key - data[lo]) * (hi - lo) / (data[hi] - data[lo]))
    pos = max(lo, min(pos, hi))
    if data[pos] == key:
        return pos
    elif data[pos] < key:
        return estimate_position(data, key, pos + 1, hi)
    else:
        return estimate_position(data, key, lo, pos - 1)

Tìm nhảy (Jump Search)

Di chuyển theo bước cố định (√n), sau đó quét tuyến tính trong đoạn nhỏ vừa xác định. Yêu cầu mảng có thứ tự. Độ phức tạp: O(√n).

import math

def leap_and_scan(data, target):
    n = len(data)
    step = int(math.isqrt(n))
    prev = 0
    while prev < n and data[min(step, n) - 1] < target:
        prev = step
        step += int(math.isqrt(n))
        if prev >= n:
            return -1
    while data[prev] < target:
        prev += 1
        if prev == min(step, n):
            return -1
    return prev if data[prev] == target else -1

Kết quả đo hiệu suất

Dưới đây là thời gian trung bình để hoàn tất một phép tìm kiếm thành công hoặc thất bại:

Hướng dẫn lựa chọn thuật toán

• Dữ liệu nhỏ (< 5.000 phần tử): Tìm tuyến tính thường nhanh hơn do chi phí khởi tạo và kiểm soát vòng lặp thấp.
• Dữ liệu vừa và lớn, đã sắp xếp: Tìm nhị phân là lựa chọn mặc định nhờ độ ổn định và hiệu năng xuất sắc trên mọi kích thước.
• Dữ liệu rất lớn và phân bố gần như tuyến tính: Tìm nội suy có thể cải thiện tốc độ thêm 15–25% so với tìm nhị phân, nhưng cần kiểm tra trước tính chất phân bố.
• Yêu cầu triển khai đơn giản và chấp nhận hiệu năng trung bình: Tìm nhảy phù hợp cho hệ thống nhúng hoặc môi trường có giới hạn tài nguyên tính toán.