Thuật toán tìm kiếm tuần tự
Bài học mô tả tìm kiếm tuần tự, vòng lặp so sánh và hai khả năng kết thúc: tìm thấy hoặc hết danh sách.
Hiểu bài
Tìm kiếm tuần tự xét lần lượt các phần tử từ đầu đến cuối danh sách, cho đến khi tìm thấy giá trị cần tìm hoặc đã hết danh sách. Với bài toán tìm địa chỉ khách hàng, đầu vào gồm danh sách và họ tên cần tìm; thuật toán xem tên đầu tiên, so sánh, rồi chuyển sang tên tiếp theo nếu chưa đúng và danh sách chưa hết.
Mô tả bằng ngôn ngữ tự nhiên:
- Xét vị trí đầu tiên.
- Nếu phần tử đang xét bằng giá trị cần tìm thì chuyển đến bước trả lời tìm thấy; nếu không, chuyển sang vị trí tiếp theo.
- Nếu chưa hết danh sách thì lặp lại phép so sánh; nếu hết thì trả lời không tìm thấy.
- Khi tìm thấy, chỉ ra vị trí phần tử và kết thúc.
Số lần lặp phụ thuộc vị trí của phần tử cần tìm. Nếu phần tử ở cuối hoặc không có trong danh sách, thuật toán có thể phải xét toàn bộ danh sách.
Sơ đồ khối tìm kiếm tuần tự: Bắt đầu, danh sách khách hàng, xem họ tên đầu tiên, kiểm tra đúng tên không, nếu đúng ghi địa chỉ, nếu hết danh sách thì không tìm thấy, rồi kết thúc. SGK trang 72