Bài 15. Thuật toán tìm kiếm nhị phân

Giải bài tập bài 15 thuật toán tìm kiếm nhị phân trang 74 sách giáo khoa Tin học lớp 7, NXB Kết nối tri thức với cuộc sống, mời các em tham khảo cùng Bumbii.

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

Hoạt động khởi động:

Việc kinh doanh mở rộng, số lượng khách hàng của cửa hàng bán giống cây trồng nhà An lên đến hàng trăm người. Việc tìm kiếm tên khách hàng trong danh sách thật khó khăn. Em có gợi ý gì cho bạn An để việc tìm kiếm được dễ dàng hơn không?

Trả lời:

Sắp xếp danh sách để tìm dễ hơn.
Đưa danh sách vào phần mềm soạn thảo văn bản hoặc bảng tính và sử dụng chức năng tìm kiếm của phần mềm để tìm kiếm.

1. THUẬT TOÁN TÌM KIẾM NHỊ PHÂN

Hoạt động 1: Sắp xếp và tìm kiếm

1. Em hãy cho biết thuật toán tìm kiếm tuần tự phải thực hiện bao nhiêu bước lặp để tìm được khách hàng tên “Trúc” trong danh sách ở Hình 15.1? Em hãy so sánh số bước lặp thực hiện của thuật toán tìm kiếm tuần tự với số bước lặp thực hiện của thuật toán tìm kiếm nhị phân.

Trả lời:

Thuật toán tìm kiếm tuần tự thực hiện 8 bước để tìm khách hàng tên “Trúc” trong danh sách ở Hình 15.1.
Thuật toán tìm kiếm nhị phân chỉ thực hiện 4 bước. Thuật toán tìm kiếm nhị phân nhanh hơn.

2. Theo em trước khi thực hiện thuật toán tìm kiếm nhị phân, danh sách khách hàng cần thoả mãn điều kiện gì? Nếu không thoả mãn điều kiện đó, thuật toán tìm kiếm nhị phân có thực hiện được không?

Trả lời:

Danh sách khách hàng cần được sắp xếp. Nếu không được sắp xếp, thuật toán tìm kiếm nhị phân không thể thu hẹp phạm vi tìm kiếm vì giá trị cần tìm có thể ở vị trí bất kì trong danh sách.

Câu hỏi

Em hãy viết các bước lặp thực hiện thuật toán tìm kiếm nhị phân để tìm khách hàng tên “Hòa” trong danh sách ở Hình 15.1.

Trả lời: Danh sách cần tìm:

Bước 1. Vị trí giữa vùng tìm kiếm là 5. So sánh “Hòa” và “Mai”. Vì H đứng trước M trong bảng chữ cái nên vùng tìm kiếm là nửa trước của dãy (từ vị trí 1 đến vị trí 4).

Bước 2. Vị trí giữa vùng tìm kiếm là 2. So sánh “Hòa” và “Bình”. Vì H đứng trước B trong bảng chữ cái nên vùng tìm kiếm là nửa sau của dãy (từ vị trí 3 đến vị trí 4).

Bước 3. Vị trí giữa vùng tìm kiếm là 3. So sánh ta thấy giá trị ở vị trí giữa đúng là “Hòa” là giá trị cần tìm. Thuật toán kết thúc.

2. SẮP VÀ TÌM KIẾM

Câu hỏi

Em hãy nêu ví dụ trong thực tế cho thấy mối liên quan giữa sắp xếp và tìm kiếm.

Trả lời: Tìm kiếm sách trong thư viện, tên sách được sắp xếp theo thứ tự của chữ cái, giúp tìm kiếm dễ dàng và nhanh chóng.

LUYỆN TẬP

1. Cho danh sách tên các nước sau đây:

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

a) Em hãy sắp xếp danh sách tên các nước theo thứ tự trong bảng chữ cái.

Trả lời: Danh sách 9 nước đã sắp xếp theo thứ tự bảng chữ cái:

b) Em hãy liệt kê các bước lặp tìm kiếm tên nước Iceland trong danh sách đã sắp xếp theo thuật toán tìm kiếm nhị phân.

Bước 1. Vị trí giữa vùng tìm kiếm là 5. So sánh “Iceland” và “Greenland”. Vì I đứng sau G trong bảng chữ cái tiếng Anh nên vùng tìm kiếm là nửa sau của dãy (từ vị trí 6 đến vị trí 7).

Bước 2. Vị trí giữa vùng tìm kiếm là 7. So sánh “Iceland” và “Portugal”. Vì I đứng trước P trong bảng chữ cái tiếng Anh nên vùng tìm kiếm là nửa trước của dãy (từ vị trí 6).

Bước 3. Vị trí giữa vùng tìm kiếm là 6. So sánh vị trí ở giữa đúng là “Iceland” là giá trị cần tìm. Thuật toán kết thúc.

c) Em hãy so sánh số bước lặp thực hiện tìm kiếm ở phần b với số bước lặp thực hiện tìm kiếm ở phần Luyện tập của bài 14.

Trả lời:

Thuật toán tìm kiếm nhị phân thực hiện 3 bước.

Theo danh sách đã sắp xếp, Iceland ở vị trí thứ 6. Nếu tìm kiếm theo thuật toán tìm kiếm tuần tự, cần thực hiện 6 bước.

Như vậy, thuật toán tìm kiếm nhị phân thực hiện nhanh hơn.

2. Em hãy cho ví dụ một bài toán tìm kiếm trong thực tế mà có thể thực hiện bằng thuật toán tìm kiếm nhị phân. Hãy thực hiện thuật toán tìm kiếm nhị phân để giải quyết bài toán đó.

Trả lời:

Ví dụ: Tìm học sinh được điểm 9,5 môn Tin học trong danh sách đã sắp xếp tăng dần.

STT	Họ tên	Điểm
1	Nguyễn Châu Anh	7,5
2	Hà Minh Đức	8,0
3	Văn Minh Hằng	8,5
4	Nguyễn Phương Chi	9,0
5	Ngô Phương Thảo	9,5
6	Ngô Hà Trang	10

Các bước thực hiện:

Vùng tìm kiếm là dãy số:

7,5

8,0

8,5

9,0

9,5

Bước 1: Chọn phần tử ở giữa, đó là 8,5. So sánh ta có 9,5 > 8,5, do đó vùng tìm kiếm thu hẹp chỉ còn nửa sau của danh sách.

7,5

8,0

8,5

9,0

9,5

Bước 2: Chọn phần tử ở giữa, đó là 9,5. So sánh ta có 9,5 = 9,5, tìm thấy giá trị cần tìm nên thuật toán dừng lại.

7,5

8,0

8,5

9,0

9,5

VẬN DỤNG

Em tìm một từ tiếng Anh trong quyển từ điển theo cách nào? Tại sao em lại dùng cách đó?

Trả lời:

Để tìm một từ tiếng Anh trong quyển từ điển bằng cách chia đổi quyển từ điển, tìm một từ bất kì ở giữa quyển từ điển.
So sánh từ cần tìm với từ bất kì ở giữa quyển từ điển. Dựa vào thứ tự chữ cái trong tiếng Anh, ta xác định giới hạn vùng tìm kiếm là nửa trước hay nửa sau của quyển từ điển.
Tiếp tục, tìm từ bất kì ở giữa của vùng tìm kiếm mới. So sánh từ cần tìm với từ bất kì ở giữa của vùng tìm kiếm mới. Dựa vào thứ tự chữ cái trong tiếng Anh, ta xác định vùng tìm kiếm mới tiếp theo.
Cứ lặp lại như thế, cho đến khi từ bất kì ở giữa của vùng tìm kiếm mới giống với từ cần tìm. Thuật toán kết thúc.
Dùng thuật toán tìm kiếm nhị phân để giảm số bước tìm kiếm, nhanh chóng tìm ra từ tiếng Anh cần tìm trong quyển từ điển.