Tin học 7 Cánh diều Bài 2: Tìm kiếm nhị phân

- Ý 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ử đã xếp thứ tự không giảm 6, 12, 18, 42, 44, 55, 67, 94. Bảng dưới minh họa từng bước chia đôi dần để tìm kiếm.

- Minh họa các bước:

- Mô phỏng thuật toán tìm kiếm nhị phân

+ L­ượt thứ nhất: a_giữa là a4 = 42; 42 < 44 = x

→ vùng tìm kiếm thu hẹp trong phạm vi từ a5 → a8;

+ L­ượt thứ hai: a_giữa là a6 = 55; 55 > 44

→ vùng tìm kiếm thu hẹp trong phạm vi là a5

+ L­ượt thứ ba: a_giữa là a5 = 44; 44 = 44 = x

→ Vậy số cần tìm là i = 5.

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

- Ý tưởng: Chia đôi dần để giảm nhanh phạm vi tìm kiếm.

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

Một mô tả của thuật toán tìm kiếm nhị phân

- Khi bắt đầu thuật toán, phạm vi tìm kiếm là dãy đã cho ban đầu. Lấy phần tử đứng giữa dãy là am để so sánh với x. Nếu a_m = x thì kết thúc. Trái lại, sẽ có hai trường hợp:

+ Nếu am < x thì chắc chắn không có x trong nửa đầu của dãy.

+ Nếu x < am thì chắc chắn không có x trong nửa sau của dãy.

→ Lặp lại theo cách như thế cho đến khi hoặc tìm thấy hoặc độ dài dãy phạm vi tìm kiếm là bằng 0.

- Để 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ị”

- 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 đó, cho đến đi nhận được kết quả.

Bài tập 1: Tìm kiếm nhị phân là gì?

Hướng dẫn giải:

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.

Bài tập 2: Vì sao tìm kiếm nhị phân nhanh hơn tìm kiếm tuần tự?

Hướng dẫn giải:

Tìm kiếm nhị phân nhanh hơn tìm kiếm tuần tự vì: Dãy đã được sắp xếp và 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.

Bài tập 3: Điều kiện để áp dụng thuật toán nhị phân là gì?

Hướng dẫn giải:

Điều kiện để áp dụng thuật toán nhị phân là dãy đã được sắp xếp tăng dần hoặc giảm dần.

Qua bài học các em có thể:

- Mô phỏng được hoạt độn 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

Các em có thể hệ thống lại nội dung kiến thức đã học được thông qua bài kiểm tra Trắc nghiệm Tin học 7 Cánh diều Chủ đề F Bài 2 cực hay có đáp án và lời giải chi tiết. 

• Câu 1:

  Tìm kiếm nhị phân là gì?

  • A. Tìm kiếm lần lượt từ đầu tới cuối dãy
  • B. Tìm kiếm ở đầu dãy
  • C. 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
  • D. Tìm kiếm ở cuối dãy

• Câu 2:

  Tìm kiếm nhị phân nhanh hơn tìm kiếm tuần tự vì sao?

  • A. Chỉ tìm kiếm trong nửa dãy còn lại
  • B. Dãy đã được sắp xếp
  • C. Cả A và B đều đúng
  • D. Cả A và B đều sai

• Câu 3:

  Bài toán nào sau đây áp dụng được thuật toán tìm kiếm nhị phân?

  • A. Cho dãy 1, 3, 5, 6. Tìm vị trí của số 5 trong dãy
  • B. Cho dãy 1, 5, 3, 6. Tìm vị trí của số 5 trong dãy
  • C. Cho dãy 6, 5, 4, 3, 2,1. Hãy tìm xem số 3 có trong dãy này không
  • D. Cả A và C

Câu 4-10: Mời các em đăng nhập xem tiếp nội dung và thi thử Online để củng cố kiến thức về bài học này nhé!

Các em có thể xem thêm phần hướng dẫn Giải bài tập Tin học 7 Cánh diều Chủ đề F Bài 2 để giúp các em nắm vững bài học và các phương pháp giải bài tập.

Khởi động trang 81 SGK Tin học 7 Cánh diều - CD

Hoạt động trang 81 SGK Tin học 7 Cánh diều - CD

Luyện tập trang 83 SGK Tin học 7 Cánh diều - CD

Vận dụng trang 83 SGK Tin học 7 Cánh diều - CD

Câu hỏi tự kiểm tra 1 trang 83 SGK Tin học 7 Cánh diều - CD

Câu hỏi tự kiểm tra 2 trang 83 SGK Tin học 7 Cánh diều - CD

Trong quá trình học tập nếu có thắc mắc hay cần trợ giúp gì thì các em hãy comment ở mục Hỏi đáp, Cộng đồng Tin học HOC247 sẽ hỗ trợ cho các em một cách nhanh chóng!

Chúc các em học tập tốt và luôn đạt thành tích cao trong học tập!