Giải SGK Tin học 7 Bài 15 (Kết nối tri thức): Thuật toán tìm kiếm nhị phân

1. Tóm tắt kiến thức cần nhớ trước khi làm bài

Bài 15 tiếp nối Bài 14 (tìm kiếm tuần tự). Nếu tìm tuần tự là “lật từng trang một” thì tìm nhị phân giống như em mở quyển từ điển ngay giữa rồi quyết định lật về phía trước hay phía sau.

• Điều kiện bắt buộc: danh sách đã được sắp xếp (theo bảng chữ cái, hoặc số tăng dần/giảm dần).
• Ý tưởng: xét phần tử ở vị trí giữa, so sánh với giá trị cần tìm, rồi chỉ giữ lại nửa có thể chứa giá trị đó.
• Điều kiện dừng: tìm thấy giá trị cần tìm, hoặc phần danh sách còn lại không còn phần tử nào (kết luận là không có).

Em có thể xem phần tóm tắt đầy đủ hơn ở bài lý thuyết tương ứng: Lý thuyết Tin học 7 Bài 15.

2. Các bước của thuật toán tìm kiếm nhị phân

1. Đặt phạm vi tìm kiếm là cả danh sách (từ vị trí đầu đến vị trí cuối).
2. Nếu phạm vi không còn phần tử nào: kết luận không tìm thấy và kết thúc.
3. Xác định vị trí giữa của phạm vi. Nếu số phần tử chẵn, em chọn một trong hai vị trí giữa và giữ nguyên cách chọn đó trong cả bài.
4. So sánh giá trị cần tìm với phần tử ở vị trí giữa:
   • Bằng nhau: kết luận tìm thấy và kết thúc.
   • Giá trị cần tìm đứng trước (nhỏ hơn): thu hẹp phạm vi về nửa trước, quay lại bước 2.
   • Giá trị cần tìm đứng sau (lớn hơn): thu hẹp phạm vi về nửa sau, quay lại bước 2.

3. Ví dụ minh hoạ tự đặt: tìm số 27

Cho dãy đã sắp xếp tăng dần gồm 9 số (đây là ví dụ do thầy đặt, không phải số liệu trong sách): 3, 8, 12, 15, 21, 27, 34, 40, 46. Hãy tìm số 27.

Bước	Phạm vi xét	Vị trí giữa	So sánh	Kết quả
1	Vị trí 1 đến 9	5 (giá trị 21)	27 > 21	Tìm nửa sau
2	Vị trí 6 đến 9	7 (giá trị 34)	27 < 34	Tìm nửa trước
3	Vị trí 6 đến 6	6 (giá trị 27)	27 = 27	Tìm thấy, dừng

Chỉ cần 3 lần so sánh, trong khi tìm tuần tự phải duyệt 6 phần tử mới gặp số 27.

Trường hợp không có: tìm số 10 trong cùng dãy. Bước 1 xét vị trí 5 (21 > 10) nên giữ vị trí 1–4. Bước 2 xét vị trí 2 (8 < 10) nên giữ vị trí 3–4. Bước 3 xét vị trí 3 (12 > 10) nên phạm vi còn lại rỗng. Kết luận: không có số 10 trong dãy.

4. Giải bài tập trong SGK

Câu hỏi 1 trang 74: gợi ý cho bạn An

Danh sách khách hàng đã lên tới hàng trăm người, tìm từng tên rất mất thời gian. Em nên khuyên An sắp xếp danh sách tên khách hàng theo thứ tự bảng chữ cái. Khi đó An có thể mở danh sách ở khoảng giữa, thấy tên đứng trước hay sau tên cần tìm rồi thu hẹp dần, giống cách tra từ điển. Xem thêm: Câu hỏi 1 trang 74.

Câu hỏi trang 76: các bước tìm khách hàng tên “Hòa” ở Hình 15.1

Danh sách ở Hình 15.1 đã được sắp xếp theo thứ tự chữ cái và có 9 khách hàng. Em trình bày theo đúng khuôn của thuật toán:

1. Bước 1: xét tên ở vị trí giữa của cả danh sách (vị trí số 5). Đối chiếu thứ tự chữ cái: “Hòa” đứng trước tên này nên chỉ giữ nửa đầu.
2. Bước 2: xét vị trí giữa của nửa đầu (vị trí số 3). Đây chính là tên “Hòa”.
3. Tìm thấy nên thuật toán kết thúc sau 2 bước.

Lưu ý: khi nửa đầu có 4 phần tử, vị trí giữa có thể là 2 hoặc 3. Em cứ chọn một cách thống nhất và nhớ đối chiếu với tên thật ở Hình 15.1 trong sách. Xem thêm: Câu hỏi trang 76.

Hoạt động 2 trang 77

Ý 1. Với tìm kiếm tuần tự, số bước bằng đúng số thứ tự của “Trúc” trong danh sách, vì phải xét lần lượt từ tên đầu tiên cho đến khi gặp. Em đếm vị trí của Trúc ở Hình 15.1 để ra con số cụ thể. Với tìm kiếm nhị phân trên danh sách 9 tên, dù tên cần tìm ở đâu cũng không quá 4 bước. Vì vậy khi tên nằm ở nửa sau danh sách, nhị phân thường cho số bước ít hơn rõ rệt.

Ý 2. Danh sách khách hàng phải được sắp xếp theo một thứ tự nhất định (ví dụ theo bảng chữ cái). Nếu danh sách chưa sắp xếp thì không thể thực hiện tìm kiếm nhị phân, vì khi so sánh với phần tử giữa em không thể biết nên bỏ nửa nào. Xem thêm: Hoạt động 2 trang 77.

Câu hỏi trang 77: liên quan giữa sắp xếp và tìm kiếm

Sắp xếp là bước chuẩn bị để tìm kiếm nhanh. Một vài ví dụ: từ điển xếp theo chữ cái nên tra từ nhanh; danh bạ điện thoại xếp theo tên; sổ điểm xếp theo số thứ tự; thư viện xếp sách theo mã nên dễ tìm. Em chỉ cần nêu một ví dụ và chỉ ra “nhờ đã xếp thứ tự nên tìm nhanh”. Xem thêm: Câu hỏi trang 77.

Luyện tập 1 trang 77: danh sách tên các nước

a) Sắp xếp theo bảng chữ cái:

Albania, Bolivia, Canada, Germany, Greenland, Iceland, Portugal, Scotland, Vietnam.

(Mẹo: Germany đứng trước Greenland vì so sánh chữ thứ hai: “e” đứng trước “r”.)

b) Tìm “Iceland” bằng thuật toán tìm kiếm nhị phân:

1. Bước 1: danh sách có 9 phần tử, vị trí giữa là 5 (Greenland). Iceland đứng sau Greenland nên tìm ở nửa sau (vị trí 6 đến 9).
2. Bước 2: vị trí giữa của vị trí 6–9 là vị trí 7 (Portugal). Iceland đứng trước Portugal nên giữ lại vị trí 6.
3. Bước 3: chỉ còn vị trí 6 là Iceland. Tìm thấy, kết thúc.

c) So sánh: tìm nhị phân mất 3 bước. Ở Bài 14, nếu tìm Iceland trên danh sách ban đầu (Bolivia, Albania, Scotland, Canada, Vietnam, Iceland, …) thì Iceland nằm ở vị trí thứ 6 nên tìm tuần tự mất 6 bước. Vậy tìm nhị phân cần ít bước hơn. Xem thêm: Luyện tập 1 trang 77.

Luyện tập 2 trang 77: bài toán thực tế dùng tìm kiếm nhị phân

• Tra một từ trong từ điển hoặc một tên trong danh bạ đã xếp theo chữ cái.
• Tìm một học sinh trong danh sách lớp đã xếp theo số báo danh.
• Trò chơi đoán số từ 1 đến 100: mỗi lần đoán số ở giữa và nghe gợi ý “lớn hơn” hay “nhỏ hơn”.

Điểm chung: dữ liệu đã có thứ tự. Xem thêm: Luyện tập 2 trang 77.

Vận dụng trang 77: tra từ tiếng Anh trong từ điển

Thông thường em mở sách ra khoảng giữa, nhìn chữ cái đầu của từ ở đó rồi quyết định lật về phía A hay phía Z, sau đó lặp lại trên phần còn lại. Cách này chính là tìm kiếm nhị phân, được dùng vì từ điển có hàng chục nghìn từ đã xếp theo thứ tự chữ cái; đọc từng từ từ đầu sẽ rất lâu. Xem thêm: Vận dụng trang 77.

5. Vì sao tìm nhị phân nhanh hơn tìm tuần tự?

Sau mỗi bước, số phần tử cần xét giảm đi khoảng một nửa. Vì vậy số bước tối đa tăng rất chậm so với độ dài danh sách:

Số phần tử	Tìm tuần tự (tối đa)	Tìm nhị phân (tối đa)
7	7 bước	3 bước
15	15 bước	4 bước
1 000	1 000 bước	10 bước
1 000 000	1 000 000 bước	20 bước

Em có thể nhớ nhanh: cứ thêm gấp đôi số phần tử thì tìm nhị phân chỉ thêm khoảng 1 bước.

6. Lỗi sai thường gặp

• Quên sắp xếp trước khi tìm. Đây là lỗi nặng nhất, khiến kết quả sai.
• Xác định vị trí giữa sai khi số phần tử chẵn. Hãy chọn thống nhất và ghi rõ vị trí đang xét.
• Quên loại bỏ phần tử giữa hoặc bỏ nhầm nửa khi so sánh. Nhớ: giá trị cần tìm nhỏ hơn thì đi về phía đầu danh sách.
• Không kết luận “không tìm thấy” khi phạm vi đã hết phần tử.

7. Bài tập tự luyện (có đáp án)

Bài 1. Cho dãy tăng dần: 2, 5, 9, 14, 20, 26, 31, 37, 45. Liệt kê các bước tìm số 37 bằng tìm kiếm nhị phân.

Đáp án: bước 1 xét vị trí 5 (giá trị 20), 37 > 20 nên lấy vị trí 6–9; bước 2 xét vị trí 7 (giá trị 31), 37 > 31 nên lấy vị trí 8–9; bước 3 xét vị trí 8 (giá trị 37), bằng nhau nên tìm thấy sau 3 bước.

Bài 2. Với cùng dãy ở Bài 1, tìm số 30. Kết quả ra sao?

Đáp án: vị trí 5 (20 < 30) lấy vị trí 6–9; vị trí 7 (31 > 30) lấy vị trí 6–6; vị trí 6 (26 < 30) nên phạm vi rỗng. Kết luận: không có số 30 trong dãy (sau 3 lần so sánh).

Bài 3. Danh sách chứa 100 học sinh đã xếp theo thứ tự. Tìm nhị phân cần tối đa bao nhiêu bước?

Đáp án: 7 bước, vì 2⁶ − 1 = 63 < 100 ≤ 127 = 2⁷ − 1.

8. Tài liệu học tiếp

• Bài 14: Thuật toán tìm kiếm tuần tự
• Bài 16: Thuật toán sắp xếp
• Vở thực hành Tin học 7 Bài 15
• Giải SBT Tin học 7 Bài 15
• Trắc nghiệm Tin học 7 Bài 15
• Giải SGK Tin học 7 – Kết nối tri thức (mục lục)

Câu hỏi thường gặp

Tìm kiếm nhị phân có dùng được khi danh sách chưa sắp xếp không?

Không. Thuật toán dựa vào thứ tự để biết nên bỏ nửa nào sau mỗi lần so sánh, nên danh sách phải được sắp xếp trước (tăng dần, giảm dần hoặc theo bảng chữ cái).

Tìm kiếm nhị phân khác tìm kiếm tuần tự ở điểm nào?

Tìm tuần tự xét lần lượt từng phần tử từ đầu danh sách. Tìm nhị phân luôn xét phần tử ở giữa rồi loại bỏ một nửa danh sách, nên cần ít bước hơn nhiều khi danh sách dài.

Khi nào thuật toán tìm kiếm nhị phân kết thúc?

Khi phần tử ở giữa bằng giá trị cần tìm (tìm thấy), hoặc khi phạm vi còn lại không còn phần tử nào (kết luận không có giá trị đó trong danh sách).

Danh sách có 1000 phần tử thì tìm nhị phân cần tối đa bao nhiêu bước?

Tối đa 10 bước, vì 2^9 − 1 = 511 nhỏ hơn 1000 và 2^10 − 1 = 1023 lớn hơn hoặc bằng 1000.

Bài học liên quan

• Ô tính, khối ô tính là gì? Cách xác định địa chỉ ô và khối ô
• Bài trình chiếu là tập hợp các trang chiếu – giải thích và ví dụ
• Mỗi bảng tính gồm có bao nhiêu trang tính?
• Phần mềm bảng tính có chức năng chính là gì? Giải thích và ví dụ
• 20 câu trắc nghiệm Tin học 7 Cánh diều Bài 2: Các thiết bị vào – ra
• Giải SBT Tin học 7 Bài 6 Kết nối tri thức: Làm quen với phần mềm bảng tính