Bài giảng môn Tin học Lớp 7 - Chủ đề F - Bài 1: Tìm kiếm nhị phân

BÀI 2 
TÌM KIẾM NHỊ PHÂN 
MỞ ĐẦU 
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? 
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? 
HOẠT ĐỘNG 
Câu trả lời: 
	Đ ồng ý với ý kiến của bạn Thanh An vì chúng ta chỉ cần chia đôi dần dãy số đã sắp thứ tự và lần lượt tìm kiếm trong phạm vi phù hợp để tìm ra kết quả mà chúng ta mong muốn thì chỉ cần 3 lần là có thể tìm ra kết quả. 
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ố 
Ví dụ 1: Tìm x = 44 trong dãy 8 phần tử đã sắp xếp thứ tự không giảm 
Minh họa các bước: 
a 1 
a 2 
a 3 
a 4 
a 5 
a 6 
a 7 
a 8 
Xuất phát 
6 
12 
18 
42 
44 
55 
67 
94 
Bước 1 
42 
44 
55 
67 
94 
Bước 2 
44 
55 
Bươc 3 
44 
Mô phỏng thuật toán tìm kiếm nhị phân 
a 1 
a 2 
a 3 
a 4 
a 5 
a 6 
a 7 
a 8 
a 
6 
12 
18 
42 
44 
55 
67 
94 
i 
  1 
2 
3 
4 
5 
6 
7 
8 
L­ượt thứ nhất : a giữa là a 4 = 42; 42 < 44 = x   vùng tìm kiếm thu hẹp trong phạm vi từ a 5  a 8 ; 
x = 44 
42 
44 
55 
67 
94 
55 
L­ượt thứ hai: a giữa là a 6 = 55; 55 > 44  vùng tìm kiếm thu hẹp trong phạm vi là a 5 
5 
44 
L­ượt thứ ba: a giữa là a 5 = 44; 44 = 44 = x 	 Vậy số cần tìm là i = 5. 
10 
9 
8 
7 
6 
5 
4 
3 
2 
1 
i 
33 
31 
30 
22 
21 
9 
6 
5 
4 
2 
A 
L­ượt thứ nhất : a giữa là a 5 = 9; 9 < 21   vùng tìm kiếm thu hẹp trong phạm vi từ a 6  a 10 ; 
33 
31 
30 
22 
21 
L­ượt thứ hai: a giữa là a 8 = 30; 30 > 21 vùng tìm kiếm thu hẹp trong phạm vi từ a6  a7; 
L­ượt thứ ba: a giữa là a 6 = 21; 21= 21 	 Vậy số cần tìm là i = 6. 
22 
21 
6 
6 
21 
Ví dụ 2: Tìm x = 21 trong dãy 10 phần tử đã sắp xếp thứ tự không giảm 
- 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: 
2 . Thuật toán tìm kiếm nhị phâ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 vị trí 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 
Thuật toán tìm kiếm nhị phân chỉ áp dụng được cho dãy đã sắp thứ tự 
Ghi nhớ 
Em hãy quan sát đoạn video sau và cho biết ý nghĩa của câu chuyện? 
TÌNH HUỐNG 
- Để 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 đó. Áp dụng liên tiếp cách này cho đến khi nhận được kết quả. 
3. Phương pháp chia để trị với bài toán tìm kiếm 
Bài 1. 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. 
Gợi ý: Có thể trình bày thông tin mô tả dưới dạng bảng như trong bài học 
Bài 2. 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? 
LUYỆN TẬP 
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 
Câu 1. 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? 
VẬN DỤNG