Giới Thiệu

Thuật toán Tìm kiếm Tuần tự (Linear Search) là một trong những thuật toán tìm kiếm đơn giản và cơ bản nhất trong lập trình. Thuật toán này được sử dụng để tìm một phần tử cụ thể trong danh sách hoặc mảng bằng cách duyệt qua từng phần tử từ đầu đến cuối. Linear Search không yêu cầu danh sách phải được sắp xếp, làm cho nó rất dễ triển khai và sử dụng trong nhiều tình huống khác nhau.

Ý Tưởng

Thuật toán Tìm kiếm Tuần tự hoạt động bằng cách kiểm tra từng phần tử trong danh sách một cách tuần tự để tìm phần tử mục tiêu. Nếu phần tử mục tiêu được tìm thấy, thuật toán trả về chỉ số của nó; nếu không, thuật toán tiếp tục kiểm tra cho đến khi hết danh sách. Nếu phần tử không có trong danh sách, thuật toán sẽ báo không tìm thấy.

Ví Dụ

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

public class LinearSearchExample {
    // Phương thức thực hiện tìm kiếm tuần tự
    public static int linearSearch(int[] arr, int target) {
        // Duyệt qua từng phần tử trong mảng
        for (int i = 0; i < arr.length; i++) {
            // So sánh phần tử hiện tại với mục tiêu
            if (arr[i] == target) {
                return i; // Trả về chỉ số của phần tử nếu tìm thấy
            }
        }
        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 = {34, 7, 23, 32, 5};
        int target = 23;

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

        int index = linearSearch(array, target);

        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 Tuần Tự

Độ 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 ở vị trí đầu tiên của danh sách)
• Trung bình: O(n) (Khi phần tử mục tiêu nằm ở giữa hoặc phải kiểm tra toàn bộ danh sách)
• Trường hợp xấu: O(n) (Khi phần tử mục tiêu nằm ở cuối danh sách hoặc không có trong danh sách)

Không gian bộ nhớ sử dụng: O(1) (Chỉ sử dụng một lượng bộ nhớ cố định, không cần bộ nhớ phụ lớn)

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

Cách sử dụng:

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

• Danh sách không được sắp xếp: Khi làm việc với danh sách hoặc mảng không được sắp xếp, thuật toán này hoạt động hiệu quả mà không cần phải sắp xếp trước.
• Danh sách nhỏ hoặc không cần tối ưu hóa: Khi danh sách có kích thước nhỏ, việc sử dụng Tìm kiếm Tuần tự có thể là lựa chọn hợp lý vì đơn giản và dễ triển khai.
• Khi không có yêu cầu đặc biệt về hiệu suất: Khi không cần xử lý nhanh chóng với danh sách lớn, tìm kiếm tuần tự có thể đáp ứng đủ yêu cầu.

Tìm kiếm tuần tự là một thuật toán đơn giản và dễ hiểu, thích hợp cho các bài toán nhỏ hoặc khi danh sách chưa được sắp xếp. Tuy nhiên, nó không hiệu quả với các danh sách lớn và không tối ưu về mặt hiệu suất so với các thuật toán tìm kiếm khác như tìm kiếm nhị phân.