Thuật toán tìm kiếm tuyến tính (Linear Search)

Tìm kiếm tuyến tính (Linear Search) là một thuật toán đơn giản, dùng để tìm kiếm một giá trị trong một danh sách (ví dụ: array) theo cách tuần tự từ đầu đến cuối.

Ý tưởng thuật toán tìm kiếm tuyến tính

Thuật toán này kiểm tra từng phần tử của danh sách cho đến khi tìm thấy giá trị cần tìm hoặc kiểm tra hết toàn bộ danh sách.

Đây là một thuật toán tôi thường xuyên sử dụng để tìm giá trị mong muốn trong 1 mảng có kích thước vừa và nhỏ.

Ví dụ thuật toán tìm kiếm tuyến tính bằng Java

public class LinearSearch {
    public static void main(String[] args) {
        int[] arr = {55, 12, 3, 67, 89, 99, 1};
        int target = 99;

        int result = linearSearch(arr, target);

        if (result == -1) {
            System.out.println("Không tìm thấy " + target + " trong mảng.");
        } else {
            System.out.println(target + " được tìm thấy tại vị trí " + result);
        }
    }

    public static int linearSearch(int[] arr, int target) {
        for (int i = 0; i < arr.length; i++) {
            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
    }
}

Hàm này duyệt qua từng phần tử của mảng và so sánh với target.

1. Nếu tìm thấy, nó trả về chỉ số của phần tử đó.
2. Nếu không tìm thấy, nó trả về -1.

Nhược điểm của tìm kiếm tuyến tính:

1. Không phù hợp cho danh sách lớn: Trong trường hợp danh sách có hàng ngàn hoặc triệu phần tử, tìm kiếm tuyến tính trở nên chậm và không hiệu quả. Thời gian tìm kiếm sẽ tăng theo tỷ lệ với kích thước danh sách.
2. Không thích hợp cho tìm kiếm nhiều lần: Nếu bạn cần thực hiện nhiều lần tìm kiếm trên cùng một danh sách, tìm kiếm tuyến tính không phải là lựa chọn tốt, vì bạn phải lặp lại toàn bộ quá trình tìm kiếm mỗi lần.
3. Không tận dụng tính chất sắp xếp của danh sách: Tìm kiếm tuyến tính không tận dụng thông tin về sự sắp xếp của danh sách. Trong trường hợp danh sách đã được sắp xếp trước, thuật toán tìm kiếm tuyến tính không thể tận dụng được tính chất này để tối ưu hóa tìm kiếm.

Trong những trường hợp cần tìm kiếm nhanh chóng trong danh sách lớn hoặc cần thực hiện nhiều lần tìm kiếm, các thuật toán tìm kiếm nâng cao như tìm kiếm nhị phân hoặc sử dụng cơ sở dữ liệu hoặc cấu trúc dữ liệu khác có thể là lựa chọn tốt hơn để giảm thời gian tìm kiếm.

Nên lựa chọn thuật toán tìm kiếm nào?

Lựa chọn thuật toán tìm kiếm phù hợp phụ thuộc vào nhiều yếu tố như:

• Kích thước tập dữ liệu
• Cấu trúc dữ liệu
• Loại dữ liệu
• Yêu cầu về hiệu quả
• Khả năng triển khai

Ví dụ:

• Tìm kiếm tuyến tính phù hợp cho tập dữ liệu nhỏ.
• Tìm kiếm nhị phân phù hợp cho tập dữ liệu lớn được sắp xếp.
• Tìm kiếm băm phù hợp cho tập dữ liệu lớn và phân bố đều.
• Tìm kiếm trên cây phù hợp cho dữ liệu có cấu trúc phân cấp.

Các bài viết không xem thì tiếc:

• Thuật toán tìm kiếm nhị phân (Binary Search)
• Cách dùng AsyncTask trong Android
• Làm việc với font trong Android
• Cách dùng Eventbus để truyền dữ liệu trong Android
• Hiểu về cách tổ chức file, bộ nhớ của app Android
• Truyền dữ liệu giữa các Activity trong android
• 7 lời khuyên của Sam Altman để thành công
• Lập trình với Recyclerview trong Android – Bài 2 | dotrinh.com
• Copy mảng byte trong Java bằng Arrays.copyOfRange()
• Truyền dữ liệu giữa 2 fragment trong android
• Chuyển một đối tượng sang Json trong Android
• Gửi dữ liệu đến BLESerial3 bằng Bluetooth LE Android
• Danh sách công ty phần mềm làm cho thị trường Nhật của Việt Nam
• Lập trình với Recyclerview trong Android – Bài 1 | dotrinh.com
• Siêu tổng hợp android code snippets (cập nhật thường xuyên)