THUẬT TOÁN TÌM KIẾM TUẦN TỰ
Định nghĩa
Thuật toán tìm kiếm tuần tự 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.
Phân tích
Thuật toán tìm kiếm tuần tự là một giải thuật đơn giản, rất dễ cài đặt, tuy nhiên nhược điểm của nó nằm ở độ phức tạp. Bắt đầu từ đối tượng a1, duyệt qua tất cả các đối tượng, cho tới khi tìm thấy đối tượng có khóa mong muốn, hoặc duyệt hết toàn bộ dãy mà không tìm thấy khóa đó.
Điều kiện để dừng thuật toán: Thuật toán tìm kiếm tuần tự thực hiện tìm lần lượt từ đầu đến cuối danh sách, chừng nào chưa tìm thấy và chưa tìm hết thì còn tìm tiếp.
Công việc
- Thuật toán tìm kiếm tuần tự thực hiện công việc tìm kiếm dữ liệu cho trước trong một danh sách đã cho bằng cách xem xét mục dữ liệu đầu tiên, sau đó xem xét lần lượt từng mục dữ liệu tiếp theo cho đến khi tìm thấy mục dữ liệu được yêu cầu hoặc đến khi hết danh sách.
Ứng dụng
- 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,...
5.Mô tả thuật toán
- Mô tả thuật toán tìm kiếm tuần tự bằng ngôn ngữ tự nhiên:
Bước 1. Xét phần tử đầu tiên của danh sách.
Bước 2. Nếu giá trị của phần tử đang xét bằng giá trị cần tìm thì chuyển sang Bước 4, nếu không thì thực hiện bước tiếp theo (Bước 3) .
Bước 3. Kiểm tra đã hết danh sách chưa. Nếu đã hết danh sách thi chuyển sang Bước 5, nếu chưa thì lặp lại từ Bước 2.
Bước 4. Trả lời “Tìm thấy” và chỉ ra vị trí phần tử tìm được; Kết thúc.
Bước 5. Trả lời “không tìm thấy"; Kết thúc.
6.Ví dụ
Sơ đồ khối mô tả thuật toán tìm kiếm tuần tự một số trong một dãy thẻ số