Tìm kiếm tuyến tính
Tìm kiếm tuyến tính là điều bạn làm khi tìm một cái tên trong danh sách chưa sắp xếp: bắt đầu từ trên cùng và đọc xuống cho đến khi thấy. Đây là cách tìm kiếm đơn giản nhất, dùng được cho mọi danh sách, và với danh sách ngắn thì thường là đủ.
Ý tưởng
So sánh giá trị cần tìm với giá trị đầu tiên của danh sách. Nếu bằng nhau, dừng lại: giá trị cần tìm ở vị trí 1. Nếu không, so sánh với giá trị thứ hai, rồi thứ ba, và cứ thế. Nếu giá trị cuối cùng cũng không khớp, giá trị cần tìm không có trong danh sách. Không cần biết trước gì về danh sách: nó không phải được sắp xếp, và các giá trị có thể là bất cứ thứ gì so sánh bằng nhau được.
Ví dụ
Tìm 4 trong 5, 1, 4, 2, 8. 5 có bằng 4 không? Không. 1 thì sao? Không. 4? Có: tìm thấy ở vị trí 3 sau 3 phép so sánh. Giờ tìm 7 trong cùng danh sách. Cả năm giá trị đều được kiểm tra và không giá trị nào khớp, nên sau 5 phép so sánh, câu trả lời là 7 không có ở đó.
Bao nhiêu phép so sánh
Giá trị ở vị trí k cần k phép so sánh để tìm thấy. Nếu giá trị cần tìm có khả năng ở mọi vị trí như nhau, trung bình là (n + 1)/2 phép so sánh: 20,5 với 40 giá trị. Giá trị không có luôn cần n, vì chỉ sau phép so sánh cuối cùng mới chắc chắn không giá trị nào khớp. Vậy chi phí tăng tỉ lệ với độ dài danh sách, được viết là O(n).
Tìm nhanh hơn cần có thứ tự
Tìm kiếm tuyến tính không thể bỏ qua gì cả, vì trong danh sách chưa sắp xếp, giá trị nào cũng có thể ở bất cứ đâu. Khi danh sách đã được sắp xếp, một phép so sánh cho biết nhiều hơn là bằng hay không: nó cho biết giá trị cần tìm nằm ở phía nào. Tìm kiếm nhị phân dùng điều đó để chia đôi danh sách ở mỗi bước và cần khoảng log₂ n phép so sánh, tối đa 6 với 40 giá trị. Tuy vậy, sắp xếp cũng tốn thời gian, nên với danh sách chỉ tìm một lần, tìm kiếm tuyến tính thường là lựa chọn tốt hơn.
Cải tiến nhỏ
Phiên bản lính canh đặt giá trị cần tìm ở cuối danh sách trước khi tìm, nên vòng lặp chỉ cần kiểm tra có khớp không, mà không cần kiểm tra cả việc đã đến cuối danh sách chưa. Mỗi lần tìm thấy một giá trị, dời nó lên trước một vị trí, hoặc lên đầu, giúp các giá trị hay được tìm ngày càng rẻ hơn. Cả hai cách đều không thay đổi trường hợp xấu nhất là n phép so sánh.
Khám phá
Mở ứng dụng, chọn một giá trị ở Tìm, rồi nhấn Bước. Đường nét đứt cho thấy độ cao của giá trị cần tìm, mỗi giá trị được tô sáng khi được kiểm tra và mờ đi khi đã bị loại, còn giá trị khớp chuyển sang màu xanh lá. Tìm một giá trị không có trong danh sách để xem một lượt trọn vẹn, hoặc tắt Dừng khi khớp lần đầu và dùng ít giá trị khác nhau để tìm nhiều giá trị khớp.
Câu hỏi thường gặp
Độ phức tạp thời gian của tìm kiếm tuyến tính là bao nhiêu?
O(n) trong trường hợp xấu nhất và trung bình, và O(1) trong trường hợp tốt nhất, khi giá trị cần tìm là giá trị đầu tiên. Nó không cần thêm bộ nhớ.
Tìm kiếm tuyến tính và tìm kiếm nhị phân khác nhau thế nào?
Tìm kiếm tuyến tính kiểm tra lần lượt mọi giá trị và dùng được cho mọi danh sách. Tìm kiếm nhị phân chỉ dùng được cho danh sách đã sắp xếp, nhưng ở mỗi bước nó chia đôi phần có thể chứa giá trị cần tìm, nên chỉ cần khoảng log₂ n phép so sánh thay vì tối đa n.
Tìm kiếm tuyến tính có cần danh sách đã sắp xếp không?
Không. Đó là ưu điểm chính của nó. Với danh sách đã sắp xếp, nó có thể dừng ngay khi vượt qua vị trí lẽ ra có giá trị cần tìm, nhưng vẫn chậm hơn tìm kiếm nhị phân.
Tìm kiếm tuyến tính được dùng ở đâu?
Ở bất cứ đâu danh sách ngắn hoặc chưa sắp xếp: tìm một phần tử trong mảng nhỏ, quét một tệp hay một luồng dữ liệu chỉ đọc được theo thứ tự, hoặc kiểm tra mọi phần tử theo một điều kiện. Nhiều hàm thư viện, như indexOf trong JavaScript và list.index trong Python, là tìm kiếm tuyến tính.
Sẵn sàng thử chưa?
Mở PictorX trong trình duyệt — không cần cài đặt, không cần thẻ tín dụng để bắt đầu.
Thử tìm kiếm tuyến tính