Bài 21. Thuật toán tìm kiếm tuần tự
Bài học giới thiệu bài toán tìm kiếm trong một dãy dữ liệu, và thuật toán đơn giản nhất để giải quyết bài toán đó - tìm kiếm tuần tự - cùng cách cài đặt bằng Python.
- Cánh DiềuTin học 11 (Khoa học máy tính) - Chủ đề F(CS) · Bài 7. Lập trình giải bài toán tìm kiếmtr. 117
- Kết nối tri thứcTin học 11 (Khoa học máy tính) - Bài 19. Bài toán tìm kiếmtr. 89–93
Bắt đầu bằng một hình dung
Giả sử bạn được phân công đón tiếp khách tại một buổi hội thảo. Trên bàn có một tờ danh sách đăng ký, ghi tên hơn một trăm người theo đúng thứ tự họ đăng ký trực tuyến - hoàn toàn không được sắp xếp theo bảng chữ cái. Khi một người bước tới và đọc tên mình, bạn phải xác định xem tên đó có trong danh sách hay không, và nếu có thì ở dòng thứ mấy để đánh dấu.
Vì danh sách không hề được sắp xếp, cách duy nhất chắc chắn đúng là dò từng dòng một: đọc dòng 1, so tên; chưa khớp thì đọc dòng 2, so tên; cứ như vậy cho đến khi gặp đúng tên cần tìm (dừng lại, biết ngay vị trí), hoặc đọc hết toàn bộ danh sách mà vẫn không thấy (kết luận người này chưa đăng ký). Cách dò tuần tự từng dòng một như vậy - đơn giản nhưng có thể mất khá nhiều thời gian nếu danh sách dài và tên cần tìm nằm ở cuối - chính là ý tưởng của thuật toán mà ta sẽ tìm hiểu trong bài này.
Nội dung bài học
- Bài toán tìm kiếm
- Ý tưởng của tìm kiếm tuần tự
Tóm tắt lý thuyết cần nhớ
- Tìm kiếm tuần tự duyệt lần lượt từng phần tử của dãy từ đầu đến cuối, so sánh với giá trị cần tìm.
- Nếu gặp phần tử khớp, thuật toán trả về ngay vị trí (chỉ số) của phần tử đó và dừng lại, không xét tiếp.
- Nếu duyệt hết dãy mà không gặp, thuật toán kết luận ‘không có’ (trong Python thường trả về
-1). - Ưu điểm là đơn giản và dùng được cả với dãy chưa sắp xếp; nhược điểm là chậm khi dãy dài mà giá trị cần tìm ở gần cuối hoặc không tồn tại.
Thuật ngữ tiếng Anh trong bài
| Tiếng Anh | Đọc là | Nghĩa |
|---|---|---|
| search | XƠ-chờ | tìm kiếm Đi tìm xem một phần tử có trong dãy hay không - giống tìm một cuốn sách trên giá sách đầy ắp. |
| algorithm | AL-gô-rít-thầm | thuật toán Các bước làm một việc theo đúng thứ tự để ra kết quả - như công thức pha mì gói: đổ nước sôi, chờ 3 phút, rồi ăn. |
Câu hỏi trắc nghiệm có đáp án
Mấy câu mẫu để bạn tự kiểm tra ngay. Trong ứng dụng, bài này có đủ 26 câu, chấm điểm tự động và giải thích từng câu sai.
- Chia đôi phạm vi tìm kiếm sau mỗi lần so sánh để loại bỏ bớt một nửa số phần tử
- Duyệt lần lượt từng phần tử của dãy theo đúng thứ tự, so sánh với giá trị cần tìm
- Sắp xếp lại dãy theo thứ tự tăng dần rồi mới bắt đầu tìm từ đầu đến cuối dãy
- Chỉ so sánh với phần tử đứng giữa dãy, nếu khác thì kết luận là dãy không có
- Xoá phần tử đó khỏi dãy rồi tìm tiếp
- Tiếp tục so sánh hết các phần tử còn lại để chắc chắn
- Trả về vị trí của phần tử đó và dừng lại ngay
- Bắt đầu lại việc so sánh từ phần tử đầu tiên
- 3
- 1
- 2
- Không tìm thấy
- a)Tìm kiếm tuần tự luôn bắt đầu so sánh từ phần tử đầu tiên của dãy trước khi xét đến các phần tử khác.Đúng
- b)Tìm kiếm tuần tự chỉ cho kết quả đúng khi dãy dữ liệu đã được sắp xếp tăng dần từ trước.Sai
- c)Trong trường hợp xấu nhất - giá trị cần tìm nằm ở cuối dãy hoặc không có trong dãy - tìm kiếm tuần tự phải so sánh với tất cả các phần tử.Đúng
- d)Nếu phần tử đầu tiên của dãy đã khớp với giá trị cần tìm, tìm kiếm tuần tự vẫn phải tiếp tục so sánh với toàn bộ các phần tử còn lại.Sai
- (a) Đúng - thuật toán luôn xuất phát từ chỉ số 0, tức phần tử đầu tiên.
- (b) Sai - tìm kiếm tuần tự vẫn cho kết quả đúng cả khi dãy chưa được sắp xếp, vì nó chỉ so sánh trực tiếp từng phần tử với giá trị cần tìm.
- (c) Đúng - khi không tìm thấy hoặc giá trị ở cuối dãy, thuật toán phải duyệt qua toàn bộ phần tử.
- (d) Sai - thuật toán dừng ngay khi gặp phần tử khớp đầu tiên, không cần so sánh tiếp.
Thử ngay: minh hoạ từng bước
Bấm từng bước để tự xem cơ chế hoạt động, hoặc bấm “Tự chạy” cho nó tiến mỗi giây một lần. Đổi được dữ liệu đầu vào - không cần đăng nhập.
Học trọn bài này trong ứng dụng
Bài giảng đầy đủ, 26 câu luyện tập chấm tự động, thi thử đúng cấu trúc đề tốt nghiệp (24 trắc nghiệm + 4 Đúng/Sai), bài thực hành máy tự chấm và gia sư AI giải thích chỗ sai.
Phần học miễn phí, không cần tạo tài khoản.
Bài liên quan - Lập trình, Thuật toán & CTDL (KHMT)
Cùng mạch kiến thức với bài này, học nối tiếp cho chắc phần lí thuyết.