Giáo án Bài 15. Thuật toán tìm kiếm nhị phân

HS nhận ra dữ liệu đã sắp xếp giúp việc tìm kiếm nhanh hơn và nêu được vấn đề: làm sao tìm một giá trị mà không phải xét lần lượt từng phần tử.

GV đưa hai dãy số: dãy A gồm 2, 5, 8, 11, 14, 17, 20 và dãy B gồm 14, 2, 20, 8, 5, 17, 11. Yêu cầu HS tìm số 11 trong mỗi dãy và ghi số lần xem phần tử. Câu hỏi GV đặt ra:

• “Em tìm 11 trong dãy A và dãy B bằng cách nào? Mỗi dãy em phải xem bao nhiêu phần tử?”
• “Nếu dãy có 1 000 số đã sắp xếp, có cách nào không cần xem từng số không?”
• “Trong dãy A, khi xem số 8 mà thấy 8 nhỏ hơn 11, em có cần xem các số 2, 5, 8 nữa không?”

HS nêu được: dãy B phải xem lần lượt từng số (đến số 11 là số thứ 7 trong dãy B); dãy A đã tăng dần nên có thể đoán vị trí của 11 nằm ở khoảng giữa và bỏ qua các số nhỏ hơn 11 ở phía trái. Kết luận sơ bộ: dữ liệu đã sắp xếp cho phép bỏ bớt một phần dãy khi tìm kiếm. Câu hỏi nêu vấn đề của bài: làm thế nào bỏ được một nửa dãy mỗi lần một cách chính xác?

HS nêu được điều kiện cần của tìm kiếm nhị phân; mô tả được cách tính vị trí giữa và quy tắc giữ nửa trái, nửa phải trên dãy tăng; giải thích được vì sao không được bỏ nửa danh sách khi dữ liệu chưa sắp xếp.

HS hoạt động nhóm 4 người với Phiếu học tập số 1 (phần A và phần B). Nhiệm vụ:

• Phần A: đọc phần “Hiểu cách hoạt động”, tính vị trí giữa khi khoảng là từ $l=1$ đến $r=7$ theo công thức $m = \lfloor \dfrac{l+r}{2} \rfloor$.
• Phần B: điền bảng quy tắc thu hẹp khoảng cho dãy tăng và dãy giảm.
  Câu hỏi GV đặt ra:
• “Vị trí giữa khi khoảng từ 1 đến 7 là bao nhiêu? Vì sao phải làm tròn xuống?”
• “Khi giá trị giữa nhỏ hơn mục tiêu trên dãy tăng, vì sao ta bỏ nửa trái?”
• “Nếu dãy giảm thì quy tắc giữ nửa nào thay đổi?”
• “Nếu dãy chưa sắp xếp, vì sao không được bỏ nửa dãy?”

Kết quả đúng:

• Phần A: $m = \lfloor \dfrac{1+7}{2} \rfloor = 4$; vị trí giữa là 4.
• Phần B (dãy tăng): giá trị giữa nhỏ hơn mục tiêu thì giữ nửa phải (các vị trí lớn hơn giữa); giá trị giữa lớn hơn mục tiêu thì giữ nửa trái (các vị trí nhỏ hơn giữa); bằng nhau thì dừng và báo vị trí.
• Dãy giảm: đổi chiều; giá trị giữa nhỏ hơn mục tiêu thì giữ nửa trái; lớn hơn mục tiêu thì giữ nửa phải.
• Điều kiện: dữ liệu chưa sắp xếp thì giá trị ở nửa bị bỏ có thể chứa mục tiêu, dẫn đến tìm sai.
  Kết luận HS rút ra: tìm kiếm nhị phân cần dãy đã sắp xếp; mỗi lần so sánh với phần tử giữa, một nửa khoảng được loại bỏ.

HS mô tả đầy đủ từng bước của thuật toán trên một dãy cụ thể; ghi được khoảng tìm kiếm, phần tử giữa, số lần so sánh và điều kiện dừng khi tìm thấy và khi không tìm thấy.

HS làm Phiếu học tập số 2 theo nhóm, dùng dãy 2, 5, 8, 11, 14, 17, 20 (vị trí từ 1 đến 7).

• Nhiệm vụ 1: tìm 11, ghi các bước vào bảng vết (khoảng, giữa, so sánh, kết luận).
• Nhiệm vụ 2: tìm 17, ghi bảng vết tương tự và đếm số lần so sánh mục tiêu với phần tử giữa.
• Nhiệm vụ 3 (mở rộng, nếu còn thời gian): tìm 18 và nhận xét khi nào khoảng tìm kiếm trở thành rỗng.
  Câu hỏi GV đặt ra:
• “Khi tìm 11, sau lần so sánh đầu tiên có cần làm gì nữa không? Vì sao?”
• “Khi tìm 17, vì sao sau lần đầu khoảng thu lại là 5 đến 7?”
• “Khi nào ta kết luận không tìm thấy?”

Bảng vết đúng:

• Tìm 11: khoảng 1 đến 7; giữa vị trí 4 (giá trị 11); 11 bằng 11 nên dừng. Kết quả: vị trí 4, 1 lần so sánh.
• Tìm 17: khoảng 1 đến 7; giữa vị trí 4 (giá trị 11) nhỏ hơn 17, giữ khoảng 5 đến 7; khoảng 5 đến 7 có giữa vị trí 6 (giá trị 17) bằng 17, dừng. Kết quả: vị trí 6, 2 lần so sánh.
• Tìm 18 (mở rộng): giữa 4 (11) nhỏ hơn 18, giữ 5 đến 7; giữa 6 (17) nhỏ hơn 18, giữ 7 đến 7; giữa 7 (20) lớn hơn 18, bỏ nửa phải, khoảng 7 đến 6 rỗng, kết luận không tìm thấy. Có 3 lần so sánh.
  Kết luận HS rút ra: điều kiện dừng là tìm thấy mục tiêu hoặc khoảng tìm kiếm rỗng.

HS củng cố điều kiện áp dụng, công thức vị trí giữa, quy tắc thu hẹp khoảng và trình tự các bước của thuật toán.

GV chiếu lần lượt các câu hỏi sau (dữ liệu dãy tăng 2, 5, 8, 11, 14, 17, 20; vị trí từ 1 đến 7, giữa làm tròn xuống). HS trả lời bằng bảng con hoặc bằng thẻ, sau đó đối chiếu trên trang bài tập tương tác của NeoEdu nếu có thiết bị.
Câu 1: Điều kiện quan trọng của tìm kiếm nhị phân là gì? A. Danh sách đã sắp theo thứ tự biết trước; B. Mọi số phải bằng nhau; C. Không được có phần tử giữa; D. Có Internet.
Câu 2: Giữa dãy 7 phần tử ở vị trí nào? A. 3; B. 4; C. 5; D. 7.
Câu 3: Dãy chưa sắp xếp vẫn luôn dùng tìm kiếm nhị phân đúng. Đúng hay sai?
Câu 4: Sau khi so sánh 11 < 17 trong dãy đã cho, có thể bỏ các vị trí 1 đến 4. Đúng hay sai?
Câu 5: Ghép khái niệm với tác dụng: nửa trái, nửa phải, khoảng rỗng.
Câu 6: Sắp xếp các bước tìm 11 theo thứ tự đúng.
Câu 7 (số liệu của Phiếu học tập số 2): Khi tìm 17 cần bao nhiêu lần so sánh mục tiêu với phần tử giữa?

Đáp án:

• Câu 1: A. Danh sách đã sắp theo thứ tự biết trước (trật tự cho phép loại một nửa danh sách một cách đúng đắn).
• Câu 2: B. Vì $\lfloor \dfrac{1+7}{2} \rfloor = 4$.
• Câu 3: Sai. Dãy chưa sắp xếp có thể bỏ nhầm nửa chứa mục tiêu.
• Câu 4: Đúng. Các giá trị 2, 5, 8, 11 đều không lớn hơn 11 nên bỏ được khi tìm 17 (vì giữa là 11 nhỏ hơn 17).
• Câu 5: Nửa trái là các vị trí nhỏ hơn giữa; nửa phải là các vị trí lớn hơn giữa; khoảng rỗng là điều kiện để kết luận không tìm thấy.
• Câu 6: Kiểm tra dãy đã tăng dần và đặt khoảng từ 1 đến 7 → Chọn giữa vị trí 4 có giá trị 11 → So sánh giá trị giữa với mục tiêu 11 → Báo vị trí 4 và kết thúc vì bằng.
• Câu 7: 2 lần so sánh (giữa 4 có giá trị 11 và giữa 6 có giá trị 17).

HS vận dụng thuật toán tìm kiếm nhị phân để giải quyết tình huống tra cứu thực tế, kiểm tra điều kiện áp dụng và giải thích kết quả.

Tình huống: Lớp có danh sách mã học sinh đã sắp xếp tăng dần gồm 12 mã: 101, 105, 109, 114, 120, 127, 133, 140, 148, 155, 163, 170. Mỗi nhóm chọn một mã cần tra cứu (một mã có trong danh sách và một mã không có trong danh sách, ví dụ 140 và 150). Nhiệm vụ:

• Ghi khoảng tìm kiếm, vị trí giữa (làm tròn xuống), so sánh và số lần so sánh cho từng mã.
• Viết 2 đến 3 câu giải thích vì sao tra cứu bằng tìm kiếm nhị phân nhanh hơn xét lần lượt trong danh sách này và điều kiện nào phải được kiểm tra trước.
  Câu hỏi GV đặt ra:
• “Vì sao danh sách mã học sinh trong trường nên được sắp xếp trước khi tra cứu?”
• “Nếu mã cần tìm không có trong danh sách, làm sao để kết luận?”

Sản phẩm mẫu với mã 140 (danh sách 12 mã, khoảng từ 1 đến 12): giữa là $\lfloor \dfrac{1+12}{2} \rfloor = 6$, giá trị 127 nhỏ hơn 140, giữ 7 đến 12; giữa là $\lfloor \dfrac{7+12}{2} \rfloor = 9$, giá trị 148 lớn hơn 140, giữ 7 đến 8; giữa là $\lfloor \dfrac{7+8}{2} \rfloor = 7$, giá trị 133 nhỏ hơn 140, giữ 8 đến 8; giữa là 8, giá trị 140 bằng 140, kết quả vị trí 8, 4 lần so sánh.
Mã 150 không có trong danh sách: khoảng rỗng sau khi thu hẹp, kết luận không tìm thấy.
Kết luận nhóm viết: tra cứu nhị phân cần danh sách đã sắp xếp; mỗi lần so sánh loại bỏ một nửa khoảng, nên số lần so sánh tăng rất chậm khi danh sách dài thêm.