Tổng quan
Linear Search (tìm kiếm tuyến tính) là thuật toán tìm kiếm đơn giản nhất. Nó quét mảng từ phần tử đầu đến phần tử cuối, so sánh từng giá trị với mục tiêu, và dừng ngay khi tìm thấy kết quả khớp.
Ưu điểm lớn của nó là tính tổng quát: không cần sắp xếp hay tiền xử lý và hoạt động trên mọi danh sách, kể cả dữ liệu chưa sắp xếp và cấu trúc liên kết. Sự linh hoạt đó đánh đổi bằng tốc độ trên dữ liệu lớn.
Tìm kiếm tuyến tính hoạt động thế nào?
- Bắt đầu tại chỉ số đầu tiên của mảng.
- So sánh phần tử hiện tại với giá trị cần tìm.
- Nếu khớp, trả về chỉ số hiện tại; việc tìm kiếm kết thúc.
- Nếu không, dịch sang phải một vị trí và lặp lại cho đến hết mảng.
- Nếu tới cuối mà không khớp, báo rằng mục tiêu không tồn tại.
Khi nào nên dùng?
- Tìm kiếm trên mảng nhỏ hoặc chưa sắp xếp khi không thể giả định về thứ tự.
- Các lần tra cứu đơn lẻ khi chi phí sắp xếp trước còn lớn hơn một lần quét.
- Dữ liệu tuần tự như danh sách liên kết hoặc luồng không hỗ trợ truy cập ngẫu nhiên.
Phân tích độ phức tạp
Linear Search chạy trong thời gian O(n) ở trường hợp trung bình và xấu nhất, vì nó có thể phải xét mọi phần tử trước khi tìm thấy mục tiêu hoặc kết luận rằng nó không tồn tại. Trường hợp tốt nhất là O(1) khi kết quả khớp nằm ở vị trí đầu tiên. Nó dùng O(1) bộ nhớ phụ và không đòi hỏi sắp xếp.
Câu hỏi thường gặp
Khi nào nên dùng Linear Search thay vì Binary Search?
Dùng Linear Search khi mảng nhỏ, chưa sắp xếp, hoặc khi bạn chỉ tìm một lần — việc sắp xếp dữ liệu chỉ để chạy tìm kiếm nhanh hơn thường tốn kém hơn một lần quét O(n) duy nhất.
Linear Search có cần mảng đã sắp xếp không?
Không. Nó so sánh từng phần tử bất kể thứ tự, và đó chính là lý do nó là lựa chọn hàng đầu cho các tập hợp chưa sắp xếp.