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

PHẦN I. HỆ THỐNG CÂU HỎI, BÀI TẬP TRONG SGK

MỞ ĐẦU

Khởi động: 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?

1. 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 Đáp án chuẩn 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 Đáp án chuẩn đượ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à Đáp án chuẩn được. Em đồng ý với Thành An không? Vì sao?

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.

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

VẬN DỤNG

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?

TỰ KIỂM TRA

Tự kiểm tra 1: Hãy mô tả quy trình chia đôi dần để thực hiện tìm kiếm nhị phân?

Tự kiểm tra 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.

PHẦN II. 5 PHÚT TRẢ LỜI CÂU HỎI, BÀI TẬP SGK

MỞ ĐẦU

Đáp án KD: 

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Ự 

Đáp án HD: 

Em đồng ý với Thành An vì dãy số đã sắp xếp không giảm. Ta chia đôi dãy số, loại bỏ nửa không chứa phần tử cần tìm và tiếp tục tìm kiếm trong nửa còn lại theo cách tương tự.

LUYỆN TẬP

Đáp án LT:

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 → chỉ cần tìm trong nửa sau của dãy (A5 đến A8).

• Chia đôi lần 2. Lấy A6 có vị trí giữa dãy. Vì x >A6 → 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. Lấy A7 có vị trị giữa dãy. Kết thúc thuật toán: Không tìm thấy x có trong dãy.

VẬN DỤNG

Đáp án VD: 

Giả sử từ điển có 262,144 mục từ. Theo thuật toán tìm kiếm nhị phân, sau mỗi lần chia đôi, phạm vi tìm kiếm giảm một nửa. Cần chia đôi 17 lần để phạm vi còn 1 mục từ. Đây là tìm kiếm nhị phân.

TỰ KIỂM TRA

Đáp án TKT1: 

- Bắt đầu thuật toán, lấy phần tử giữa so sánh với x.

+ Nếu phần tử đó là x, kết luận: Đã tìm thấy x và kết thúc.

+ Nếu không, xác định x không có trong nửa đầu hoặc nửa sau, thu hẹp phạm vi tìm kiếm.

- Lặp lại quá trình tìm x trong phạm vi thu hẹp cho đến khi tìm thấy.

Đáp án TKT2: 

Không phải 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.