Chuyển tới nội dung chính

Tìm Kiếm Tuyến Tính (Linear Search)

Bạn sẽ học được gì

Tìm kiếm tuyến tính (linear search) là thuật toán tìm kiếm cơ bản nhất: đi từ đầu đến cuối, xem từng phần tử cho tới khi gặp mục tiêu. Đơn giản đến mức ai cũng nghĩ ra — nhưng hiểu rõ khi nào nó là lựa chọn đúng (và khi nào không) mới là điều quan trọng. Đây cũng là bàn đạp để bạn trân trọng sức mạnh của tìm kiếm nhị phân ở bài sau.

1. Trực quan: tìm chìa khoá trong túi áo​

Hãy tưởng tượng bạn đánh rơi chùm chìa khoá vào một chiếc túi tối có nhiều ngăn xếp thành hàng. Bạn không nhìn thấy gì, cũng không biết các ngăn được sắp xếp ra sao. Cách duy nhất hợp lý là: thò tay vào ngăn đầu tiên, sờ thử; không phải thì sang ngăn kế tiếp; cứ thế cho tới khi chạm đúng chùm chìa.

Đó chính là tìm kiếm tuyến tính. Không có mẹo, không nhảy cóc — chỉ quét tuần tự.

Tim so 7 trong mang:   [4]  [9]  [2]  [7]  [5]
                        ↑
buoc 1:  xem 4  -> khong phai
         [4]  [9]  [2]  [7]  [5]
              ↑
buoc 2:  xem 9  -> khong phai
         [4]  [9]  [2]  [7]  [5]
                   ↑
buoc 3:  xem 2  -> khong phai
         [4]  [9]  [2]  [7]  [5]
                        ↑
buoc 4:  xem 7  -> TIM THAY! tra ve vi tri 3

Để ý: mảng không cần sắp xếp. Đây là điểm mạnh duy nhất nhưng cực kỳ giá trị của linear search.

2. Ý tưởng cốt lõi​

Đặt một "con trỏ" chạy từ vị trí 0 đến hết mảng. Tại mỗi vị trí, so sánh phần tử hiện tại với mục tiêu. Trùng thì trả về chỉ số (index); chạy hết mà không thấy thì trả về -1 (quy ước "không có").

Tình huốngSố lần so sánhĐộ phức tạp
Mục tiêu ở đầu mảng1O(1) — tốt nhất
Mục tiêu ở giữan/2 trung bìnhO(n)
Mục tiêu ở cuối hoặc không cónO(n) — xấu nhất

Bộ nhớ phụ: O(1) — chỉ cần một biến chỉ số. Không đụng tới cấu trúc dữ liệu nào khác.

3. Chạy debug: quét tìm số 7​

Bước qua từng vòng lặp để thấy con trỏ i trượt dần và phép so sánh diễn ra thế nào.

🐞 Tìm 7 trong [4, 9, 2, 7, 5]Bước 1/7
1arr = [4, 9, 2, 7, 5]
2target = 7
3for i in range(len(arr)):
4  if arr[i] == target:
5      ket_qua = i
6      break
Biến tại bước này
arr[4, 9, 2, 7, 5]
👉 Mảng ban đầu, chưa cần sắp xếp.

4. Code chạy được​

Hàm trả về chỉ số nếu tìm thấy, ngược lại trả -1. Thử đổi target để xem các trường hợp.

Đang tải trình chạy code…

5. Mẹo Sentinel (lính canh)​

Trong vòng lặp trên, mỗi vòng làm hai việc kiểm tra: "đã hết mảng chưa?" và "có trùng không?". Mẹo sentinel loại bỏ kiểm tra biên bằng cách đặt chính mục tiêu vào cuối mảng làm "lính canh". Khi đó vòng lặp chắc chắn sẽ dừng (vì cùng lắm sẽ trùng với lính canh), nên ta không cần điều kiện biên nữa.

Đang tải trình chạy code…

Sentinel không đổi độ phức tạp (vẫn O(n)) nhưng giảm số phép so sánh trong mỗi vòng — một tối ưu hằng số nho nhỏ, hữu ích khi mảng rất lớn.

6. Phân tích: khi nào dùng, bẫy thường gặp​

Khi nào nên dùng linear search:

  • Dữ liệu chưa sắp xếp và bạn chỉ tìm một lần (sắp xếp để dùng nhị phân sẽ tốn hơn — sắp xếp là O(n log n)).
  • Mảng nhỏ (vài chục phần tử) — chênh lệch tốc độ không đáng kể, code đơn giản dễ đúng.
  • Cần tìm mọi vị trí trùng, không chỉ một (nhị phân không tự nhiên làm điều này).
  • Cấu trúc không cho phép truy cập ngẫu nhiên theo chỉ số, ví dụ danh sách liên kết (xem bài 2.2.1) — bạn buộc phải đi tuần tự.

Bẫy thường gặp:

  • Quên trả -1 khi không tìm thấy, dẫn tới trả về giá trị rác.
  • Tưởng linear search "chậm" nên né tránh ngay cả với mảng nhỏ — đôi khi nó là lựa chọn đúng và sạch nhất.
  • Nhầm rằng linear search cần mảng sắp xếp. Không — đó là điểm khác biệt cốt lõi so với nhị phân.

7. Mẫu nhận diện​

  • Dữ liệu chưa sắp xếp + chỉ tìm một lần → linear search.
  • Mảng rất nhỏ → đừng phức tạp hoá, quét tuần tự là đủ.
  • Cần đếm/liệt kê tất cả phần tử thoả điều kiện → quét tuyến tính tự nhiên hơn.
  • Đi qua danh sách liên kết hoặc luồng dữ liệu (stream) không có chỉ số → bắt buộc tuyến tính.

Ngược lại, nếu mảng đã sắp xếp và bạn tìm nhiều lần, hãy nghĩ ngay tới tìm kiếm nhị phân — nhanh hơn rất nhiều (O(log n) thay vì O(n)).

8. 🎮 Trò chơi: Hiểu linear search​

🎮 Hiểu tìm kiếm tuyến tínhCâu 1/4· Điểm 0· 🔥 0

Quét tuần tự từ đầu đến cuối, O(n). Không cần mảng sắp xếp.

In ra gì?

def f(arr, t):
    for i in range(len(arr)):
        if arr[i] == t:
            return i
    return -1
print(f([5, 2, 9], 8))

9. Quiz kiểm tra nhanh​

📝 Quiz kiểm tra nhanh
1. Độ phức tạp xấu nhất của tìm kiếm tuyến tính là?
2. Ưu điểm lớn nhất của linear search so với tìm kiếm nhị phân là?
3. Mẹo sentinel (lính canh) giúp ích gì?

10. Hoàn thành​

…

☑️ Tiếp theo: 3.2.2 — Tìm kiếm nhị phân (nhanh hơn rất nhiều, nhưng đòi mảng đã sắp xếp).