Giải Tin Học 7 trang 75
Lời giải chi tiết SGK Lớp 7 · Môn Tin Há»c · Trang 75–76
Bài 15: Thuật toán tìm kiếm nhị phân
Tóm tắt nội dung lý thuyết
Trang 74 giới thiệu về thuật toán tìm kiếm nhị phân (còn gọi là tìm kiếm chia đôi):
Ý tưởng chính:
- Khi danh sách đã được sắp xếp theo thứ tự, ta không cần tìm từ đầu đến cuối
- Thay vào đó, ta so sánh giá trị cần tìm với giá trị ở giữa danh sách
- Nếu bằng → tìm thấy, dừng lại
- Nếu lớn hơn → chỉ cần tìm ở nửa sau danh sách
- Nếu nhỏ hơn → chỉ cần tìm ở nửa đầu danh sách
- Lặp lại cho đến khi tìm thấy hoặc hết danh sách
💡 Mẹo nhớ: "Chia đôi, so giữa, bỏ nửa" - Mỗi bước loại bỏ một nửa danh sách!
Hoạt động 1: Sắp xếp và tìm kiếm
Câu 1
Đề bài: Em hãy cho biết thuật toán tìm kiếm tuần tự phải thực hiện bao nhiêu bước lặp để tìm được khách hàng tên "Trúc" trong danh sách ở Hình 15.1? Em hãy so sánh số bước lặp thực hiện của thuật toán tìm kiếm tuần tự với số bước lặp thực hiện của thuật toán tìm kiếm nhị phân.
Cách giải
Bước 1: Xác định số bước của tìm kiếm tuần tự
Danh sách khách hàng theo thứ tự tên (đã sắp xếp):
| Vị trí | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|
| Tên | An | Bình | Hoà | Liên | Mai | Phương | Trang | Trúc | Tước |
Tìm kiếm tuần tự: Duyệt từ đầu đến cuối, so sánh lần lượt:
- Bước 1: So sánh với "An" → Không phải
- Bước 2: So sánh với "Bình" → Không phải
- Bước 3: So sánh với "Hoà" → Không phải
- Bước 4: So sánh với "Liên" → Không phải
- Bước 5: So sánh với "Mai" → Không phải
- Bước 6: So sánh với "Phương" → Không phải
- Bước 7: So sánh với "Trang" → Không phải
- Bước 8: So sánh với "Trúc" → Tìm thấy!
→ Tìm kiếm tuần tự cần 8 bước lặp
Bước 2: Xác định số bước của tìm kiếm nhị phân
Theo ví dụ trong sách:
- Bước 1: So sánh "Trúc" với "Mai" (vị trí 5) → Tìm nửa sau
- Bước 2: So sánh "Trúc" với "Trang" (vị trí 7) → Tìm nửa sau
- Bước 3: So sánh "Trúc" với "Trúc" (vị trí 8) → Tìm thấy!
→ Tìm kiếm nhị phân chỉ cần 3 bước lặp
Bước 3: So sánh
| Thuật toán | Số bước lặp |
|---|---|
| Tìm kiếm tuần tự | 8 bước |
| Tìm kiếm nhị phân | 3 bước |
Đáp án: - Tìm kiếm tuần tự cần 8 bước lặp - Tìm kiếm nhị phân chỉ cần 3 bước lặp - Tìm kiếm nhị phân nhanh hơn tìm kiếm tuần tự (ít hơn 5 bước)
Câu 2
Đề bài: Theo em trước khi thực hiện thuật toán tìm kiếm nhị phân, danh sách khách hàng cần thoả mãn điều kiện gì? Nếu không thoả mãn điều kiện đó, thuật toán tìm kiếm nhị phân có thực hiện được không?
Cách giải
Phân tích:
Thuật toán tìm kiếm nhị phân hoạt động dựa trên nguyên tắc:
- So sánh giá trị cần tìm với giá trị ở giữa
- Dựa vào kết quả so sánh để quyết định tìm ở nửa trước hay nửa sau
Điều này chỉ đúng khi các phần tử được sắp xếp theo thứ tự (tăng dần hoặc giảm dần).
Ví dụ minh họa:
Nếu danh sách chưa sắp xếp: An, Trang, Mai, Trúc, Bình...
- Khi so sánh "Trúc" với phần tử giữa, ta không thể biết "Trúc" nằm ở nửa nào
- Vì các phần tử không theo thứ tự, việc loại bỏ một nửa có thể bỏ sót kết quả
Đáp án: - Điều kiện: Danh sách khách hàng phải được sắp xếp theo thứ tự (theo tên, theo họ, hoặc theo tiêu chí nào đó) trước khi thực hiện tìm kiếm nhị phân. - Nếu không thoả mãn: Thuật toán tìm kiếm nhị phân KHÔNG thể thực hiện được (hoặc nếu thực hiện sẽ cho kết quả sai).
💡 Mẹo nhớ: "Muốn chia đôi, phải xếp hàng!" - Tìm kiếm nhị phân chỉ hoạt động khi dữ liệu đã được sắp xếp.
🎯 Ghi nhớ: - Thuật toán tìm kiếm nhị phân nhanh hơn nhiều so với tìm kiếm tuần tự khi danh sách lớn - Điều kiện bắt buộc: Dữ liệu phải được sắp xếp trước khi áp dụng tìm kiếm nhị phân - Mỗi bước của tìm kiếm nhị phân loại bỏ một nửa danh sách cần xét