BÀI 2: TÌM KIẾM NHỊ PHÂN
Trang bìa
Trang bìa
TIN HỌC 7
BÀI 2: TÌM KIẾM NHỊ PHÂN
Ảnh
Khởi động
- Đặt vấn đề
Nếu phải tìm một số trong dãy đã sắp xếp theo thứ tự tăng dần hoặc giảm dần, em có cách nào tìm nhanh hơn tìm kiếm tuần tự không?
Ảnh
Hình thành kiến thức
1. Chia đôi dần để tìm kiếm một số trong dãy số đã sắp thứ tự
Ảnh
1. Chia đôi dần để tìm kiếm một số trong dãy số đã sắp thứ tự
- Có 8 thẻ, mỗi thẻ có ghi một số nguyên trên đó. Tất cả các thẻ được sắp xếp thành dãy theo thứ tự không giảm của các số ghi trên đó và đặt sấp mặt ghi số xuống bàn để em không nhìn thấy. Cô giáo đọc một số, gọi là X. - Cần trả lời câu hỏi: Có hay không một thẻ ghi số X? Hãy sử dụng ít nhất số lần lật một thẻ lên xem mà vẫn trả lời được câu hỏi. Bạn Thanh An cho rằng chỉ cần không quá ba lần lật thẻ là trả lời được. Em đồng ý với Thanh An không? Vì sao?
- Ví dụ
Ảnh
Ví dụ: Tìm x = 44 trong dãy 8 phần tử đã sắp xếp thứ tự không giảm 6, 12, 18, 42, 44, 55, 67, 94. Bảng trên minh họa từng bước chia đôi dần để tìm kiếm.
2. Thuật toán tìm kiếm nhị phân
Ảnh
2. Thuật toán tìm kiếm nhị phân
- Đọc SGK, em hãy tìm hiểu xem thế nào là thuật toán tìm kiếm nhị phân?
- Mô tả thuật toán
Mô tả một thuật toán tìm kiếm nhị phân
Ảnh
3. Phương pháp "chia để trị" với bài toán tìm kiếm
Ảnh
3. Phương pháp "chia để trị" với bài toán tìm kiếm
- Đọc SGK, em hãy cho biết cách làm "chia để trị" là như nào?
- Kết luận
Ảnh
- Tìm kiếm nhị phân là tìm kiếm bằng cách chia dãy làm hai nửa, loại bỏ nửa dãy chắc chắn không chứa phần tử cần tìm, chỉ tìm kiếm trong nửa dãy còn lại. - Khi dãy có thứ tự thì mới áp dụng được tìm kiếm nhị phân.
Kết luận
Luyện tập
- Trả lời câu hỏi (LUYỆN TẬP)
Ảnh
Cho một dãy số 5, 11, 18, 39, 41, 52, 63, 70. Hãy mô tả diễn biến từng bước tìm kiếm nhị phân để tìm kiếm x = 60 trong dãy trên.
- Trả lời câu hỏi
Ảnh
Em hãy mô tả cách tra cứu, tìm giải nghĩa một từ trong từ điển. Có thể gọi cách tìm đó là áp dụng thuật toán tìm kiếm nhị phân không?
Vận dụng
- Câu 1 (VẬN DỤNG)
Ảnh
Câu 1: Hãy mô tả quy trình chia đôi dần để thực hiện tìm kiếm nhị phân.
- Câu 2 (VẬN DỤNG)
Ảnh
Câu 2: Theo em, có phải với bất cứ dãy số nào cũng có thể áp dụng được thuật toán tìm kiếm nhị phân không? Giải thích tại sao.
Dặn dò
- Dặn dò
Ảnh
Dặn dò
- Ôn lại bài vừa học. - Làm bài tập trong SBT. - Chuẩn bị bài sau: Bài 3: Sắp xếp chọn.
- Cảm ơn
Ảnh
THANK YOU!