Giới Thiệu

Thuật toán Tìm kiếm Tam phân (Ternary Search) là một phương pháp tìm kiếm trong một danh sách đã được sắp xếp, tương tự như tìm kiếm nhị phân nhưng phân chia danh sách thành ba phần thay vì hai. Tìm kiếm tam phân hoạt động bằng cách so sánh phần tử mục tiêu với hai phần tử phân chia để xác định phạm vi tìm kiếm. Thuật toán này có thể hữu ích trong một số tình huống cụ thể nhưng thường ít được sử dụng hơn so với tìm kiếm nhị phân.

Ý Tưởng

Thuật toán Tìm kiếm Tam phân hoạt động theo cách chia danh sách thành ba phần bằng cách so sánh phần tử mục tiêu với hai phần tử phân chia, sau đó tiếp tục tìm kiếm trong phần mà phần tử mục tiêu có thể nằm. Cụ thể:

1. Chia danh sách thành ba phần bằng cách tính hai chỉ số phân chia first và second, dựa trên độ dài của danh sách.
2. So sánh phần tử mục tiêu với phần tử tại chỉ số first và second:

• Nếu phần tử mục tiêu bằng phần tử tại first hoặc second, thuật toán trả về chỉ số của phần tử đó.
• Nếu phần tử mục tiêu nhỏ hơn phần tử tại first, tiếp tục tìm kiếm trong nửa bên trái.
• Nếu phần tử mục tiêu nằm giữa first và second, tiếp tục tìm kiếm trong phần giữa.
• Nếu phần tử mục tiêu lớn hơn phần tử tại second, tiếp tục tìm kiếm trong nửa bên phải.

1. Lặp lại quá trình cho đến khi tìm thấy phần tử mục tiêu hoặc danh sách không còn phần tử nào để kiểm tra.

Ví Dụ

Dưới đây là một ví dụ về thuật toán Tìm kiếm Tam phân được triển khai bằng Java:

public class TernarySearchExample {
    // Phương thức thực hiện tìm kiếm tam phân
    public static int ternarySearch(int[] arr, int target, int left, int right) {
        if (left <= right) {
            // Tính toán hai chỉ số phân chia
            int first = left + (right - left) / 3;
            int second = right - (right - left) / 3;

            // So sánh phần tử mục tiêu với các phần tử phân chia
            if (arr[first] == target) {
                return first; // Trả về chỉ số của phần tử nếu tìm thấy
            }
            if (arr[second] == target) {
                return second; // Trả về chỉ số của phần tử nếu tìm thấy
            }

            // Tiếp tục tìm kiếm trong các phạm vi thích hợp
            if (target < arr[first]) {
                return ternarySearch(arr, target, left, first - 1);
            } else if (target > arr[second]) {
                return ternarySearch(arr, target, second + 1, right);
            } else {
                return ternarySearch(arr, target, first + 1, second - 1);
            }
        }
        return -1; // Trả về -1 nếu không tìm thấy phần tử mục tiêu
    }

    // Phương thức để in mảng
    public static void printArray(int[] arr) {
        for (int i : arr) {
            System.out.print(i + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        int[] array = {2, 4, 6, 8, 10, 12, 14, 16, 18, 20};
        int target = 14;

        System.out.println("Mảng ban đầu:");
        printArray(array);

        int index = ternarySearch(array, target, 0, array.length - 1);

        if (index != -1) {
            System.out.println("Phần tử " + target + " được tìm thấy tại chỉ số " + index);
        } else {
            System.out.println("Phần tử " + target + " không được tìm thấy trong mảng.");
        }
    }
}

Đánh Giá Thuật Toán Tìm Kiếm Tam Phân

Độ phức tạp thuật toán:

• Trường hợp tốt: O(1) (Khi phần tử mục tiêu nằm ở một trong các chỉ số phân chia)
• Trung bình: O(log₃ n) (Số lần phân chia danh sách thành ba phần)
• Trường hợp xấu: O(log₃ n) (Khi phần tử mục tiêu không có trong danh sách và phải thực hiện toàn bộ quá trình phân chia)

Không gian bộ nhớ sử dụng: O(log n) (Do tính chất đệ quy của thuật toán, nhưng ít hơn so với tìm kiếm nhị phân)

Tại chỗ (In-place): Có

Cách sử dụng:

Tìm kiếm tam phân thường được áp dụng trong các tình huống sau:

• Danh sách đã được sắp xếp: Khi danh sách đã được sắp xếp, thuật toán Tìm kiếm Tam phân hoạt động hiệu quả.
• Khi muốn thử nghiệm phương pháp phân chia khác: Khi bạn muốn thử nghiệm phân chia danh sách thành ba phần thay vì hai, Tìm kiếm Tam phân có thể là một lựa chọn thú vị.

Tìm kiếm tam phân là một phương pháp tìm kiếm hiệu quả cho các danh sách đã được sắp xếp, nhưng thường ít phổ biến hơn so với tìm kiếm nhị phân. Mặc dù nó có thể cung cấp một cách tiếp cận khác cho việc tìm kiếm, trong thực tế, tìm kiếm nhị phân thường được ưa chuộng hơn do sự đơn giản và hiệu quả của nó.