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

Giải Tin học 7 Bài 2: Tìm kiếm nhị phân

Khởi động

Khởi động trang 81 Tin học 7: Nếu phải tìm một số trong dãy đã sắp xếp theo thứ tự tăng 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?

Trả lời:

Nếu phải tìm một số trong dãy đã sắp xếp theo thứ tự tăng hoặc giảm dần, ta xem số đó ở khoảng nào trong dãy mà không sợ bỏ sót.

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

Hoạt động

Hoạt động trang 81 Tin học 7: 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 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 thẻ lên xem mà vẫn trả lời được câu hỏi. Bạn Thành 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 Thành An không? Vì sao?

Trả lời:

Em đồng ý với Thành An vì:

- Dãy số đã được sắp xếp không giảm, ta chia đôi dãy số, 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. Nửa còn lại ta làm tương tự như trước.

Luyện tập

Luyện tập trang 83 Tin học 7: Cho 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.

Có thể trình bày thông tin mô tả dưới dạng bảng như bài học.

Trả lời:

Tìm x = 60:

- Chia đôi lần 1. Phạm vi tìm kiếm từ dãy A1 đến A8. Lấy A4 là số có vị trí giữa dãy. Vì x >A4 nên nửa đầu dãy chắc chắn không chứa x = 60. Tiếp theo chỉ cần tìm trong nửa sau cảu dãy. Phạm vi tìm kiếm từ A5 đến A8.

- Chia đôi lần 2. Phạm vi tìm kiếm từ dãy A5 đến A8. Lấy A6 có vị trí giữa dãy. Vì x>A6 nên nửa đầu dãy chắc chắn không chứa x = 60. Tiếp theo chỉ cần tìm trong nửa sau của dãy. Phạm vi tìm kiếm từ A7 đến A8.

- Chia đôi lần 3. Phạm vi tìm kiếm từ A7 đến A8. Lấy A7 có vị trị giữa dãy. Vì x

Kết thúc thuật toán: Không tìm thấy x có trong dãy.

Vận dung

Vận dụng trang 83 Tin học 7: Em hãy mô tả cách tra cứu, tìm một từ trong từ điển. Có thể gọi cách tìm kiếm đó là áp dụng thuật tìm kiếm nhị phân không?

Trả lời:

Giả sử cuốn từ điển có khoảng 300 nghìn mục từ. Để dễ tính toán, ta coi là từ điển có 2¹⁸ = 262144 mục từ và được sắp xếp theo vần bảng chữ cái. Nếu tra tìm một từ trong từ điển bằng cách tìm kiếm nhị phân thì sau một lần chia đôi, phạm vi tìm kiếm giảm đi chỉ còn một nửa, tức là còn 2¹⁷ = 131072 mục từ. Dễ thấy rằng nếu theo thuật toán tìm kiếm nhị phân, ta phải chia đôi 17 lần cho đến khi phạm vi kiếm là 2⁰ = 1 mục từ mới tìm thấy. Nên có thể gọi đây là tìm kiếm nhị phân.

Câu hỏi tự kiểm tra

Câu 1 trang 83 Tin học 7: Hãy mô tả quy trình chia đôi dần để thực hiện tìm kiếm nhị phân?

Trả lời:

Mô tả quy trình chia đôi dần để thực hiệ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 để so sánh với x.

+ Nếu phần tử đó chính là x thì kết luận. Đã tìm thấy x và kết thúc thuật toán.

+ Trái lại, ta có thể xác định được x chắc chắn không có trong nửa đầu hay nửa sau của dãy, từ đó xác định được phạm vi tìm kiếm ở bước tiếp theo là nửa còn lại.

Tiếp theo, việc tìm x trong phạm vi tìm kiếm (tức là nửa dãy còn lại) sẽ được lặp lại cho cho đến khi tìm thấy hoặc độ dài cần tìm chỉ còn bằng 1 và so sánh được ngay để biết tìm thấy x hay không.

Câu 2 trang 83 Tin học 7: 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.

Trả lời:

Không 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 Vì tìm kiếm nhị phân chỉ áp dụng với dãy số đã được sắp xếp tăng dần hoặc giảm dần.

Lý thuyết Tin Học 7 Bài 2: Tìm kiếm nhị phân

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

Ý tưởng chia đôi dần để tìm một số trong một dãy số được minh họa bởi ví dụ sau đây:

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.

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, sau đó 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 từ a₅ đến a₈.

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 sau dãy 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 từ a₅.

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

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

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

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

Hình 2.1: 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à a_m để 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 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.

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.

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

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

Xem thêm lời giải bài tập Tin học lớp 7 Cánh diều hay, chi tiết khác:

Bài 3: Sắp xếp chọn

Bài 4: Sắp xếp nổi bọt

Bài 5: Thực hành mô phỏng các thuật toán tìm kiếm, sắp xếp

Bài 1: Thiết bị vào - ra cơ bản cho máy tính cá nhân

Bài 2: Các thiết bị vào

• Xem thêm tài liệu Tin học lớp 7 Cánh diều hay, chi tiết khác:

Lý thuyết Bài 2: Tìm kiếm nhị phân