Bài 2. Tìm kiếm nhị phân

Bài Tìm kiếm nhị phân trang 81 SGK Tin Học lớp 7 – Cánh Diều, mời các em tham khảo cùng Bumbii.

Chủ đề F. Giải quyết vấn đề với sự trợ giúp của máy tính. Bài 2. Tìm kiếm nhị phân.

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?

Đáp án:

Có. Dãy số đã sắp xếp theo thứ tự, ta chia đôi dãy để giảm nhanh phạm vi tìm kiếm. Hay còn gọi là cách tìm kiếm nhị phân.

CHIA ĐÔI DẦN ĐỂ TÌM KIẾM MỘT SỐ TRONG DÃY SỐ ĐÃ SẮP THỨ TỰ

Hoạt động. 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 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?

Đáp án:

Có thể. Ý tưởng chia đôi dần để tìm một số trong một dãy số đã cho.

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

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ỏ sẽ dễ hơn.

Chia để trị là một phương pháp rất hiệu quả để giải nhiều bài toán.

LUYỆN TẬP

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.

Đáp án:

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₄ (60 > 39), chỉ cần tìm trong nửa sau của dãy. Phạm vi tìm kiếm của dãy con là 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₆ (60 > 52), chỉ cần tìm trong nửa sau của dãy. Phạm vi tìm kiếm của dãy con là a₇ đến a₈.

Chia đôi lần 3: 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₇ (60 < 63), chỉ cần tìm trong nửa trước của dãy. Phạm vi tìm kiếm là dãy con chỉ còn một số a₇.

Kết thúc thuật toán với kết quả: Không tìm thấy x trong dãy đã cho.

VẬN DỤNG

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?

Đáp án: Có. Có thể áp dụng ý tưởng tìm kiếm nhị phân, vì các từ trong từ điển đã được sắp xếp theo thứ tự.

CÂU HỎI TỰ KIỂM TRA

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.

Đáp án:

Bước 1. Phạm vi tìm kiếm là dãy ban đầu

Bước 2. Lặp khi vẫn còn Phạm vi tìm kiếm

a) Xác định phần tử a_m ở giữa Phạm vi tìm kiếm

b) Nếu x = a_m:

          Thông báo tìm thấy x ở vị trí m

          Kết thúc thuật toán

Trái lại:

          Loại bỏ nửa dãy chắc chắn không chứa x

          Phạm vi tìm kiếm = nửa dãy còn lại

Hết nhánh

      Hết lặp

Bước 3. (Đã hết dãy số mà không thấy x): Thông báo không có x trong dãy.

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.

Đáp án:

Không. Vì nếu dãy đầu vào chưa sắp thứ tự thì thuật toán có thể cho kết quả sai.

Xem thêm các bài khác tại Giải bài tập sách giáo khoa Tin học lớp 7 – NXB Cánh Diều

Thông tin liên hệ & mạng xã hội:
Website: https://bumbii.com/
Facebook: https://www.facebook.com/bumbiiapp
Pinterest: https://www.pinterest.com/bumbiitech

Tuyết Nguyễn

Không bao giờ từ bỏ hy vọng. Cố gắng mỗi ngày.