Linear search là gì?

Question

Accepted Answer

**Linear search** quét một tập hợp từng phần tử một cho đến khi tìm thấy giá trị mục tiêu hoặc đến cuối. Nó hoạt động trên **bất kỳ** danh sách nào — đã sắp xếp hay chưa — nhưng chạy trong thời gian **O(n)**.

## Ý tưởng

Không giả định gì về thứ tự: chỉ cần kiểm tra từng phần tử một.

## Ví dụ

```python
def linear_search(arr, target):
    for i, value in enumerate(arr):   # duyệt từ trái sang phải
        if value == target:
            return i                  # trả về chỉ số khi tìm thấy
    return -1                         # không tìm thấy sau khi quét hết

linear_search([4, 2, 7, 1], 7)        # -> 2
```

## Độ phức tạp

- **Thời gian:** O(n) trong trường hợp xấu nhất (mục tiêu nằm cuối hoặc không có), O(1) trong trường hợp tốt nhất.
- **Bộ nhớ:** O(1).

## Khi nào dùng

- Dữ liệu **chưa được sắp xếp** và bạn không thể tốn công sắp xếp nó.
- Danh sách nhỏ, nên O(n) là không đáng kể.
- Bạn cần một lần tra cứu duy nhất mà việc xây dựng chỉ mục hoặc sắp xếp trước là không đáng.

Nếu bạn tìm kiếm nhiều lần, hãy ưu tiên một mảng đã sắp xếp với binary search hoặc một hash set để tra cứu trung bình O(1).

## Tại sao điều này quan trọng

Linear search là chuẩn cơ sở để mọi thuật toán tìm kiếm khác được đem ra so sánh.

Nó nhắc bạn rằng thuật toán *đúng* phụ thuộc vào dữ liệu: dữ liệu nhỏ và chưa sắp xếp thì hợp với phép quét đơn giản; dữ liệu lớn và bị truy vấn nhiều lần thì hợp với các cấu trúc thông minh hơn.

Biết khi nào O(n) là đủ tốt giúp ngăn việc tối ưu hóa sớm.