Cài đặt thuật toán Ternary Search trong lập trình

Trong lĩnh vực lập trình, thuật toán tìm kiếm là một công cụ mạnh mẽ giúp chúng ta giải quyết các bài toán liên quan đến tìm kiếm dữ liệu hiệu quả. Một trong những thuật toán tìm kiếm đáng chú ý là Ternary Search, hay còn gọi là tìm kiếm ba phân. Đây là một dạng cải tiến của Binary Search, nhằm tối ưu hóa quá trình tìm kiếm trong các tập dữ liệu đã được sắp xếp.

Nguyên lý hoạt động của thuật toán

Thuật toán tìm kiếm ba phân hoạt động bằng cách chia khoảng tìm kiếm thành ba phần thay vì hai phần như trong tìm kiếm nhị phân. Cụ thể, trong mỗi bước tìm kiếm, thuật toán sẽ phân chia mảng thành ba phần bằng nhau, tạo thành hai điểm so sánh. Sau đó, thuật toán sẽ quyết định tiếp tục tìm kiếm trong phần nào dựa trên giá trị của các điểm so sánh này.

Các bước thực hiện

1. Khởi tạo các biến cận:

   • L: Điểm bắt đầu của mảng.
   • R: Điểm kết thúc của mảng.

2. Xác định hai điểm so sánh:

   • mid1: Điểm chia thứ nhất, tính bằng công thức L + (R - L) / 3.
   • mid2: Điểm chia thứ hai, tính bằng công thức R - (R - L) / 3.

3. So sánh với giá trị cần tìm (key):

   • Nếu key bằng giá trị tại mid1, trả về mid1.
   • Nếu key bằng giá trị tại mid2, trả về mid2.
   • Nếu key nhỏ hơn giá trị tại mid1, tiếp tục tìm kiếm trong đoạn [L, mid1-1].
   • Nếu key lớn hơn giá trị tại mid2, tiếp tục tìm kiếm trong đoạn [mid2+1, R].
   • Nếu key nằm giữa mid1 và mid2, tiếp tục tìm kiếm trong đoạn [mid1+1, mid2-1].

4. Lặp lại quy trình cho đến khi tìm thấy giá trị hoặc đoạn mảng không còn phần tử nào.

Ví dụ minh họa

Dưới đây là một ví dụ minh họa cụ thể trong ngôn ngữ lập trình Python để cài đặt thuật toán tìm kiếm ba phân.

def ternary_search(arr, key):
    def search(L, R):
        if L > R:
            return -1  # Không tìm thấy

        mid1 = L + (R - L) // 3
        mid2 = R - (R - L) // 3

        if arr[mid1] == key:
            return mid1
        if arr[mid2] == key:
            return mid2

        if key < arr[mid1]:
            return search(L, mid1 - 1)
        elif key > arr[mid2]:
            return search(mid2 + 1, R)
        else:
            return search(mid1 + 1, mid2 - 1)

    return search(0, len(arr) - 1)

# Ví dụ sử dụng
arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
key = 7
index = ternary_search(arr, key)
print(f"Chỉ số của {key} là: {index}")  # Output: Chỉ số của 7 là: 6

Ưu điểm và nhược điểm

Ưu điểm:

• Có thể giảm số bước tìm kiếm trong một số trường hợp so với Binary Search.
• Tối ưu hóa trong các tập dữ liệu lớn với phân bổ đồng đều.

Nhược điểm:

• Độ phức tạp tính toán tăng lên do phải tính toán thêm hai điểm phân chia.
• Hiệu quả không cao hơn Binary Search quá nhiều trong thực tế.

Kết luận

Thuật toán tìm kiếm ba phân là một cải tiến đáng giá trên cơ sở các thuật toán tìm kiếm truyền thống. Mặc dù không phải lúc nào cũng vượt trội hơn, nhưng trong một số trường hợp đặc biệt, thuật toán này có thể mang lại hiệu quả cao. Nắm vững cách cài đặt và áp dụng đúng ngữ cảnh sẽ giúp bạn tối ưu hóa quá trình tìm kiếm dữ liệu trong các ứng dụng thực tế.