Tìm kiếm tuần tự

Tìm kiếm tuần tự


Phân loại giải thuật tìm kiếm
Cấu trúc dữ liệu danh sách
Độ phức tạp thời gian O(n) khi phần tử tìm kiếm nằm cuối danh sách hoặc không có trong danh sách
Thời gian chạy tốt nhất O(1) khi phần tử cần tìm nằm ngay đầu danh sách
Độ phức tạp không gian O(n)

Trong Khoa học máy tính tìm kiếm tuần tự (tiếng Anh Sequential search) hay tìm kiếm tuyến tính (tiếng Anh linear search) là một phương pháp tìm kiếm một phần tử cho trước trong một danh sách bằng cách duyệt lần lượt từng phần tử của danh sách đó cho đến lúc tìm thấy giá trị mong muốn hay đã duyệt qua toàn bộ danh sách.

Ứng dụng

[sửa | sửa mã nguồn]

Tìm kiếm tuần tự là một giải thuật rất đơn giản khi hiện thực. Giải thuật này tỏ ra khá hiệu quả khi cần tìm kiếm trên một danh sách đủ nhỏ hoặc một danh sách chưa sắp thứ tự đơn giản. Trong trường hợp cần tìm kiếm nhiều lần, dữ liệu thường được xử lý một lần trước khi tìm kiếm: có thể được sắp xếp theo thứ tự, hoặc được xây dựng theo một cấu trúc dữ liệu đặc trưng cho giải thuật hiệu quả hơn,...

Phiên bản lặp tự nhiên

[sửa | sửa mã nguồn]

Đây là phiên bản hay gặp nhất của giải thuật này, kết quả trả về sẽ là vị trí của phần tử cần tìm hoặc một giá trị Δ thể hiện việc không tìm thấy phần tử trong danh sách đó.

 1. For each item in the list:
     1. if that item has the desired value,
         1. stop the search and return the item's location.
 2. Return 'Δ

Nếu danh sách được lưu trữ dưới dạng mảng, vị trí của phần tử cần tìm có thể là chỉ số của nó trong mảng, còn giá trị Δ có thể là chỉ số nằm trước phần tử đầu tien (0 hoặc -1 tùy vào danh sách).

Nếu danh sách là một danh sách liên kết, vị trí của phần tử được trả về có thể nằm dưới dạng địa chỉ của no, còn giá trị Δ có thể là giá trị null.

Phiên bản đệ quy

[sửa | sửa mã nguồn]

Đây là phiên bản đệ quy khi hiện thực giải thuật tìm kiếm tuần tự.

 1. if the list is empty, return Λ;
 2. else
    1. if the first item of the list has the desired value
       1. return its location;
    2. else 
       1. search the value in the remainder of the list, and return the result.

Sử dụng phần tử cầm canh

[sửa | sửa mã nguồn]

Một phương pháp được sử dụng để cải thiện hiệu quả của giải thuật là chèn phần tử muốn tìm kiếm và cuối danh sách như một phần tử cầm canh (sentinel) như được trình bày dưới đây:

 1. Set A[n + 1] to x. 
 2. Set i to 1.
 3. Repeat this loop:
     1. If A[i] = x, 
        1. exit the loop.
     2. Set i to i + 1.
 4. Return i.

Việc thêm phần tử cầm canh giúp giảm bớt việc so sánh chỉ số hiện tại i với số các phần tử n ở mỗi vòng lặp. Tuy nhiên, điều này chỉ có thể được sử dụng khi vị trí cuối cùng của danh sách tồn tại nhưng chưa được sử dụng.

Tìm kiếm tuần tự trên một danh sách đã sắp xếp

[sửa | sửa mã nguồn]

Trong các danh sách đã được sắp xếp nhưng bắt buộc phải truy xuất tuần tự như danh sách liên kết hay tệp tin, việc tìm kiếm tuần tự sẽ hiệu quả hơn trong nhiều trường hợp không cần duyệt toàn bộ danh sách vẫn kết luận được phần tử đó không có mặt. Tuy nhiên, với một mảng được sắp xếp, việc tìm kiếm nhị phân tỏ ra hiệu quả trong đa số trường hợp

Tham khảo

[sửa | sửa mã nguồn]
Chúng tôi bán
Bài viết liên quan
Tam vị tương thể cấu thành nên một sinh vật trong Tensura
Tam vị tương thể cấu thành nên một sinh vật trong Tensura
Cơ thể của một sinh vật sống có xác thịt ví dụ như con người chẳng hạn, được cấu tạo bởi tam vị tương thể
Nhân vật Ryuunosuke - Sakurasou No Pet Na Kanojo
Nhân vật Ryuunosuke - Sakurasou No Pet Na Kanojo
Akasaka Ryuunosuke (赤坂 龍之介 - Akasaka Ryūnosuke) là bệnh nhân cư trú tại phòng 102 của trại Sakurasou. Cậu là học sinh năm hai của cao trung Suiko (trực thuộc đại học Suimei).
Nhân vật Chitanda Eru trong Hyouka
Nhân vật Chitanda Eru trong Hyouka
Chitanda Eru (千反田 える, Chitanda Eru) là nhân vật nữ chính của Hyouka. Cô là học sinh lớp 1 - A của trường cao trung Kamiyama.
La Dolce Vita – 5 bí kíp để tận hưởng “cuộc sống ngọt ngào” kiểu Ý
La Dolce Vita – 5 bí kíp để tận hưởng “cuộc sống ngọt ngào” kiểu Ý
Theo nghiên cứu từ Đại học Leicester, người Ý thường khoẻ mạnh và sống lâu hơn so với nhiều quốc gia Châu Âu khác. Bí mật của họ là biến mọi khoảnh khắc cuộc sống trở nên ngọt ngào và đáng nhớ. Với họ, từng phút giây ở thời điểm hiện tại đều đáng thưởng thức bằng mọi giác quan.