Thuật toán Linear Search là gì? Giải thích dễ hiểu kèm demo trực quan

Linear Search không yêu cầu mảng phải sắp xếp, cũng không cần bất kỳ cấu trúc dữ liệu đặc biệt nào. Chỉ cần duyệt tuần tự là được.

Linear Search giải bài toán gì?

• Tìm vị trí của một phần tử trong mảng.
• Kiểm tra xem phần tử có tồn tại hay không.
• Duyệt theo thứ tự để so sánh từng phần tử với giá trị cần tìm.

Ý tưởng chính của Linear Search

Thuật toán rất đơn giản:

1. Bắt đầu từ chỉ số 0.
2. So sánh phần tử hiện tại với giá trị cần tìm (key).
3. Nếu bằng → trả về vị trí / thành công.
4. Nếu không → tiếp tục với phần tử kế tiếp.
5. Nếu duyệt hết mảng mà không tìm thấy → không tồn tại.

Ví dụ minh họa

Mảng: [5, 3, 8, 4, 2, 7]
Key tìm: 4

Duyệt:
5 → không
3 → không
8 → không
4 → Tìm thấy tại index 3

Demo Linear Search bằng JavaScript

Demo thể hiện:

• Highlight phần tử đang được duyệt.
• Log từng bước so sánh.
• Thông báo khi tìm thấy hoặc không tìm thấy.

Phân tích code Linear Search

Ý tưởng code

function linearSearchWithSteps(arr, key) {
    var steps = [];

    for (var i = 0; i < arr.length; i++) {
        steps.push({
            type: "compare",
            index: i,
            value: arr[i]
        });

        if (arr[i] === key) {
            steps.push({
                type: "found",
                index: i,
                value: arr[i]
            });
            break;
        }
    }

    if (steps[steps.length - 1].type !== "found") {
        steps.push({ type: "not_found" });
    }

    return steps;
}

Khi nào nên dùng Linear Search?

• Khi mảng chưa sắp xếp.
• Khi kích thước mảng không quá lớn.
• Khi cần kiểm tra điều kiện phức tạp (không chỉ là so sánh bằng).

Kết luận

Linear Search là thuật toán đơn giản nhưng cực kỳ phổ biến. Với demo trực quan, bạn có thể thấy chính xác cách thuật toán duyệt từng phần tử và xác định kết quả.