Video giảng Tin học 7 cánh diều bài 2 Tìm kiếm nhị phân

Tóm lược nội dung

BÀI 2: TÌM KIẾM NHỊ PHÂN

Xin chào các em học sinh thân mến, chúng ta lại gặp nhau trong bài học ngày hôm nay rồi!

Thông qua video này, các em sẽ nắm được các kiến thức và kĩ năng như sau:

• Mô phỏng được hoạt động của thuật toán tìm kiếm nhị phân trên một bộ dữ liệu đầu vào có kích thước nhỏ.
• Biết được tìm kiếm nhị phân nhanh hơn tìm kiếm tuần tự.
• Nêu được ý nghĩa của việc chia một bài toán thành những bài toán nhỏ hơn.

HOẠT ĐỘNG KHỞI ĐỘNG:

Trước khi bước vào bài học ngày hôm nay, các em đọc tình huống mở đầu và trả lời câu hỏi:

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?

HOẠT ĐỘNG KHÁM PHÁ

Nội dung 1: Tìm hiểu chia đôi dần để tìm kiếm một số trong dãy số đã sắp xếp thứ tự

Các em hãy thực hiện bài tập sau:

Có 8 thẻ, mỗi thẻ ghi một số Thứ 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 chẳng hạn. 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á 3 lần lật thẻ là trả lời được. Em đồng ý với Thanh An không? Vì sao?

Video trình bày nội dung:

- Ý tưởng: chia đôi dần để tìm một số trong một dãy số

- Ví dụ: Tìm x = 44 trong dãy 8 phần tử đã sắp xếp thứ tự không giảm

- Giải thích:

+ Chia đôi lần 1: Phạm vi tìm kiếm là dãy từ a₁ đến a₈. Lấy a₄ là số có vị trí giữa dãy. Vì x > a₄ nên nửa đầu dãy chắc chắn không chứa x = 44, tiếp theo chỉ cần tìm trong nửa sau của dãy. Như vậy, phạm vi tìm kiếm tiếp theo là dãy con từ a₅ đến a₈.

+ Chia đôi lần 2: Phạm vi tìm kiếm là dãy từ a₅ đến a₈. Lấy a₆ là số có vị trí giữa dãy. Vì x < a₆ nên nửa sau chắc chắn không chứa x = 44, tiếp theo chỉ cần tìm trong nửa đầu của dãy. Như vậy, phạm vi tìm kiếm tiếp theo là dãy con chỉ còn một số a₅

=> Phạm vi tìm kiếm chỉ còn 1 số kết thúc thuật toán với kết quả: Tìm thấy x ở vị trí thứ 5

Nội dung 2: Tìm hiểu thuật toán tìm kiếm nhị phân

Các em hãy tìm hiểu thuật toán tìm kiếm nhị phân

Video trình bày nội dung:

- Thuật toán tìm kiếm nhị phân là thuật toán tìm kiếm x trong dãy đã sắp thứ tự với ý tưởng chia đôi dần để giảm nhanh phạm vi tìm kiếm.

- Mô tả thuật toán:

- Chú ý: Thuật toán tìm kiếm nhị phân chỉ áp dụng được cho dãy đã sắp thứ tự

………..

Nội dung video Bài 2: Tìm kiếm nhị phân còn nhiều phần rất hấp dẫn và thú vị. Hãy cùng đăng kí để tham gia học bài và củng cố kiến thức thông qua hoạt động luyện tập và vận dụng trong video.