Tìm hiểu về Linear Search Thuật toán tìm kiếm đơn giản và hiệu quả

Giới thiệu về Linear Search

Linear Search (tìm kiếm tuyến tính) là một trong những thuật toán tìm kiếm cơ bản và dễ hiểu nhất. Nó hoạt động bằng cách kiểm tra từng phần tử trong mảng lần lượt cho đến khi tìm thấy phần tử cần tìm hoặc kết thúc mảng.

Cách hoạt động của Linear Search

1. Bắt đầu từ phần tử đầu tiên của mảng.
2. So sánh phần tử hiện tại với phần tử cần tìm (target).
3. Nếu phần tử hiện tại bằng target, trả về chỉ số của phần tử đó.
4. Nếu phần tử hiện tại không bằng target, tiếp tục kiểm tra phần tử tiếp theo trong mảng.
5. Lặp lại các bước trên cho đến khi tìm thấy target hoặc đã kiểm tra hết tất cả các phần tử trong mảng.
6. Nếu đã kiểm tra hết tất cả các phần tử mà không tìm thấy target, trả về -1.

Cài đặt Linear Search trong JavaScript

Dưới đây là mã nguồn chi tiết của thuật toán Linear Search trong JavaScript:

function linearSearch(arr, target) {
    // Duyệt qua tất cả các phần tử trong mảng
    for (let i = 0; i < arr.length; i++) {
        // So sánh phần tử hiện tại với giá trị cần tìm
        if (arr[i] === target) {
            // Nếu tìm thấy, trả về chỉ số của phần tử
            return i;
        }
    }
    // Nếu không tìm thấy, trả về -1
    return -1;
}

// Ví dụ sử dụng:
let array = [2, 3, 4, 10, 40];
let target = 10;
let index = linearSearch(array, target);

if (index !== -1) {
    console.log(`Phần tử ${target} được tìm thấy ở chỉ số ${index}`);
} else {
    console.log(`Phần tử ${target} không có trong mảng`);
}

Giải thích mã nguồn

1. Hàm linearSearch:

   • Hàm nhận hai tham số: arr (mảng cần tìm kiếm) và target (giá trị cần tìm).
   • Sử dụng vòng lặp for để duyệt qua tất cả các phần tử trong mảng từ chỉ số 0 đến chỉ số arr.length - 1.

2. Vòng lặp for:

   • for (let i = 0; i < arr.length; i++):
     • i là biến đếm bắt đầu từ 0 và tăng lên 1 sau mỗi lần lặp.
     • arr.length là độ dài của mảng, đảm bảo rằng vòng lặp sẽ kiểm tra tất cả các phần tử trong mảng.

3. So sánh phần tử hiện tại với target:

   • if (arr[i] === target):
     • Nếu phần tử tại chỉ số i bằng với target, hàm trả về chỉ số i và kết thúc.

4. Trả về kết quả nếu không tìm thấy:

   • Nếu vòng lặp kết thúc mà không tìm thấy target, hàm trả về -1 để chỉ ra rằng phần tử cần tìm không có trong mảng.

Ví dụ minh họa

Giả sử chúng ta có mảng array = [2, 3, 4, 10, 40] và cần tìm phần tử 10.

• Lần lặp 1: Kiểm tra array[0] (2) với target (10), không khớp.
• Lần lặp 2: Kiểm tra array[1] (3) với target (10), không khớp.
• Lần lặp 3: Kiểm tra array[2] (4) với target (10), không khớp.
• Lần lặp 4: Kiểm tra array[3] (10) với target (10), khớp. Trả về chỉ số 3.

Thời gian và không gian của thuật toán

1. Thời gian:

   • O(n) trong trường hợp xấu nhất: Khi phần tử cần tìm nằm ở cuối mảng hoặc không tồn tại trong mảng, thuật toán sẽ phải kiểm tra tất cả các phần tử.
   • O(1) trong trường hợp tốt nhất: Khi phần tử cần tìm nằm ở đầu mảng.

2. Không gian:

   • O(1) vì thuật toán chỉ sử dụng một số biến phụ trợ và không yêu cầu thêm bộ nhớ ngoài mảng đầu vào.

Ưu và nhược điểm của Linear Search

Ưu điểm:

• Đơn giản, dễ hiểu và dễ triển khai.
• Không yêu cầu mảng phải được sắp xếp.

Nhược điểm:

• Hiệu suất kém với các mảng lớn vì phải duyệt qua tất cả các phần tử trong trường hợp xấu nhất.
• Không hiệu quả so với các thuật toán tìm kiếm phức tạp hơn như Binary Search (khi mảng đã được sắp xếp).

Linear Search là một thuật toán cơ bản nhưng rất hữu ích trong nhiều tình huống, đặc biệt khi mảng nhỏ hoặc các phần tử không có thứ tự cụ thể.