Giáo án điện tử tin học 7 cánh diều bài 2: Tìm kiếm nhị phân (1 tiết)

NHIỆT LIỆT CHÀO ĐÓN CÁC EM ĐẾN VỚI BÀI HỌC HÔM NAY!

KHỞI ĐỘNG

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?

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

(1 Tiết)

NỘI DUNG BÀI HỌC

Chia đôi dần để tìm kiếm một số trong dãy số đã sắp thứ tự

Thuật toán tìm kiếm nhị phân

Phương pháp “chia để trị” với bài toán tìm kiếm

  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ẻ 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 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?

Gợi ý

Ý kiến của bạn Thanh An là chính xác. Vì khi chia đôi để tìm một số trong dãy, ta có thể tìm được kết quả nhanh hơn. Nên sẽ không tìm quá ba lần lật thẻ.

Em hãy đọc ví dụ trong mục 1 SGK tr.81, 82 và trình bày lại ý tưởng chia đôi dần để tìm một số trong một dãy số.

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₅.

2. Thuật toán tìm kiếm

Đọc thông tin mục 2 SGK tr.82, quan sát hình 2 trả lời câu hỏi:

• Thuật toán tìm kiếm nhị phân là gì?
• Mô tả cách tìm kiếm của thuật toán tìm kiếm nhị phân
• Lấy một ví dụ thực tế có thể áp dụng thuật toán tìm kiếm nhị phân.

KẾT LUẬN

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

• Phạm vi tìm kiếm là dãy ban đầu.
• Lấy phần tử đứng giữa dãy là a_m = để so sánh với x. Nếu a_m = x thì kết thúc. Trái lại, có hai trường hợp:
  • Nếu a_m < x thì chắc chắn không có x trong nửa đầu của dãy;
  • Nếu x < a_m thì chắc chắn không có x trong nửa sau của dãy.
• Tiếp theo chỉ cần tìm trong nửa dãy còn lại.
• Chú ý
• Thuật toán tìm kiếm nhị phân chỉ áp dụng được cho dãy đã sắp thứ tự.

3. Phương pháp “chia để trị” với bài toán tìm kiếm

Để giải một bài toán lớn, người ta tìm cách chia bài toán ban đầu ra thành các bài toán nhỏ hơn rồi giải những bài toán nhỏ hơn sẽ dễ hơn. Cách làm này gọi là “chia để trị”.

Đọc thông tin mục 3 trong SGK tr.83, trình bày về thuật toán tìm kiếm nhị phân.

Ghi nhớ

Thuật toán tìm kiếm nhị phân chia bài toán ban đầu thành hai bài toán con nhỏ hơn và chỉ phải tiếp tục giải một trong hai bài toán con đó. Áp dụng liên tiếp cách này cho đến khi nhận được kết quả.