Tìm hiểu Linear Search trong JavaScript và cách triển khai

Tìm kiếm tuyến tính (Linear Search) là một thuật toán tìm kiếm đơn giản. Ý tưởng chính là duyệt qua từng phần tử của mảng và so sánh nó với giá trị cần tìm. Nếu tìm thấy, trả về chỉ số của phần tử đó; nếu không, trả về -1.

Dưới đây là cách triển khai Linear Search trong JavaScript:

function linearSearch(arr, target) {
    for (let 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
}

// Ví dụ sử dụng:
let array = [10, 23, 45, 70, 11, 15];
let target = 45;
let result = linearSearch(array, target);

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

Giải thích:

1. Khởi tạo vòng lặp for:

   • Vòng lặp chạy từ i = 0 đến arr.length - 1, duyệt qua tất cả các phần tử của mảng.

2. So sánh phần tử hiện tại với giá trị cần tìm:

   • if (arr[i] === target): Kiểm tra nếu phần tử tại chỉ số i bằng với giá trị cần tìm (target).

3. Trả về kết quả:

   • Nếu tìm thấy phần tử, trả về chỉ số của phần tử đó (return i).
   • Nếu không tìm thấy sau khi duyệt qua toàn bộ mảng, trả về -1 (return -1).

Thời gian và không gian:

• Thời gian: O(n) trong trường hợp xấu nhất, vì có thể phải duyệt qua toàn bộ mảng để tìm phần tử.
• Không gian: O(1) vì không sử dụng thêm không gian bộ nhớ ngoài mảng đầu vào và biến target.

Linear Search là một thuật toán đơn giản và dễ hiểu, nhưng không hiệu quả với các mảng lớn. Trong trường hợp mảng đã được sắp xếp, có thể sử dụng thuật toán Tìm kiếm nhị phân (Binary Search) để cải thiện hiệu suất.