BÀI 15: THUẬT TOÁN TÌM KIẾM NHỊ PHÂN (15 CÂU)

I. NHẬN BIẾT (2 CÂU)

Câu 1: Thuật toán tìm kiếm nhị phân là gì.

Trả lời:

- Thuật toán tìm kiếm nhị phân là thuật toán thực hiện tìm trên danh sách đã được sắp xếp theo thứ tự từ nhỏ đến lớn. Bát đầu từ vị trí ở giữa danh sách.

- Tại mỗi bước lặp, so sánh giá trị cần tìm với giá trị của vị trí giữa danh sách, nếu bằng thì dừng lại, nếu nhỏ hơn thì tìm trong nửa trước của danh sách, nếu lớn hơn thì tìm trong nửa sau của danh sách.

- Chừng nào chưa tìm thấy và vùng tìm kiếm còn phần tử thì còn tiếp tục.

Câu 2: Hãy mô tả thuật toán tìm kiếm nhị phân.

Trả lời:

Bước 1: Nếu vùng tìm kiếm không có phần tử nào thì kết luận không tìm thấy và thuật toán kết thúc.

Bước 2: Xác định vị trí giữa của vùng tìm kiếm. Vị trí này chia vùng tìm kiếm thành hai nửa: nửa trước và nửa sau vị trí giữa.

Bước 3: Nếu giá trị cần tìm bằng giá trị của vị trí giữa thì kết luận “giá trị cần tìm xuất hiện tại vị trí giữa” và kết thúc.

Bước 4: Nếu giá trị cần tìm nhỏ hơn giá trị của vị trí giữa thì vùng tìm kiếm mới được thu hẹp lại, chỉ còn nửa trước của dãy. Ngược lại, nếu giá trị cần tìm lớn hơn giá trị của vị trí giữa thì vùng tìm kiếm mới được thu hẹp lại, chỉ còn nửa sau của dãy.

Bước 5: Lặp lại từ Bước 1 đến Bước 4 cho đến khi tìm thấy giá trị cần tìm (Bước 3) hoặc vùng tìm kiếm không còn phần tử nào (Bước 1).

II. THÔNG HIỂU (5 CÂU)

Câu 1: Sự khác nhau giữa thuật toán tìm kiếm tuần tự và thuật toán tìm kiếm nhị phân là gì?

Trả lời:

Sự khác nhau giữa thuật toán tìm kiếm tuần tự và thuật toán tìm kiếm nhị phân là: Thuật toán tuần tự sẽ không yêu cầu danh sách cần phải được sắp xếp nhưng thuật toán tìm kiếm nhị phân cần danh sách phải được sắp xếp thì mới có thể thực hiện được.

Câu 2: Thuật toán tìm kiếm nhị phân được sử dụng trong trường hợp nào?
Trả lời:

Thuật toán tìm kiếm nhị phân được sử dụng trong trường hợp danh sách đã được sắp xếp và yêu cầu đi tìm một phần tử bất kì.

Câu 3: Chọn câu diễn đạt đúng hoạt động của thuật toán tìm kiếm nhị phân.

1. Tìm trên danh sách đã sắp xếp, bắt đầu từ đầu danh sách, chừng nào chưa tìm thấy hoặc chưa tìm hết thì còn tìm tiếp.
2. Tìm trên danh sách đã sắp xếp, bắt đầu từ giữa danh sách, chừng nào chưa tìm thấy hoặc chưa tìm hết thì còn tìm tiếp.
3. Tìm trên danh sách bất kì, bắt đầu từ giữa danh sách, chừng nào chưa tìm thấy hoặc chưa tìm hết thì còn tìm tiếp.
4. Tìm trên danh sách bất kì, bắt đầu từ đầu danh sách, chừng nào chưa tìm thấy hoặc chưa tìm hết thì còn tìm tiếp.

Trả lời:

Đáp án đúng là B.

Câu 4: Hãy ghép mỗi nội dung ở cột A với những nội dung phù hợp ở cột B để xác định đầu vào và đầu ra của thuật toán tìm kiếm nhị phân.

Trả lời:

1-c 1-d 2-a 2-b

Câu 5: Em hãy điền các cụm từ:

[giá trị cần tìm xuất hiện ở vị trí giữa, nửa sau, “Không tìm thấy”, nửa trước]

vào chỗ chấm (...) trong các câu sau để được mô tả chính xác về thuật toán tìm kiếm nhị phân:

1. a) Bước 1: Nếu vùng tìm kiếm không có phần tử nào thì kết luận … và thuật toán kết thúc.
2. b) Bước 2: Xác định vị trí giữa của vùng tìm kiếm. Vị trí này chia vùng tìm kiếm thành hai nửa: nửa trước và nửa sau vị trí giữa.
3. c) Bước 3: Nếu giá trị cần tìm bằng giá trị của vị trí giữa thì kết luận … và kết thúc.
4. d) Bước 4: Nếu giá trị cần tìm nhỏ hơn giá trị của vị trí giữa thì vùng tìm kiếm mới được thu hẹp lại, chỉ còn … của dãy.

Ngược lại, nếu giá trị cần tìm lớn hơn giá trị của vị trí giữa thì vùng tìm kiếm mới được thu hẹp lại, chỉ còn … của dãy.

1. e) Bước 5: Lặp lại từ Bước 1 đến Bước 4 cho đến khi tìm thấy giá trị cần tìm (Bước 3) hoặc vùng tìm kiếm không còn phần tử nào (Bước 1).

Trả lời:

1. a) “Không tìm thấy”
2. b) giá trị cần tìm xuất hiện ở vị trí giữa
3. c)  nửa trước - nửa sau

III, VẬN DỤNG (6 CÂU)

Câu 1: 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:

Trong thực tế trong quản lý học sinh, danh sách học sinh luôn được sắp xếp theo chữ cái đầu của tên để dễ tìm kiếm.

Câu 2: Thuật toán tìm kiếm nhị phân cần bao nhiêu bước để tìm thấy “Mai" trong danh sách ["Hoa”, ”Lan”, "Ly”, ”Mai”, ”Phong”, ”Vi]?

Trả lời:

Bước 1: Xét vị trí ở giữa của dãy, đó là vị trí số 3.

So sánh “Ly” và “Mai”. Vì “L” đứng trước “M” trong bảng chữ cái nên bỏ đi nửa đầu danh sách.

Bước 2: Xét vị trí ở giữa của nửa sau danh sách, đó là vị trí số 5.

So sánh “Phong” và “Mai”. Vì “P” đứng sau “M” trong bảng chữ cái nên bỏ đi nửa sau danh sách.

Bước 3: Xét vị trí ở giữa của dãy giữa sau danh sách, đó là vị trí số 4.

So sánh “Mai” và “Mai”. Vì hai giá trị bằng nhau nên thuật toán kết thúc

=> Sau 3 bước đã tìm thấy “Mai” trong danh sách.

Câu 3: Thuật toán tìm kiếm nhị phân cần thực hiện bao nhiêu bước lặp để thông báo không tìm thấy số 15 trong danh sách [3, 5, 7, 11, 12, 25]?
Trả lời:

Bước 1: Xét vị trí ở giữa của dãy, đó là vị trí của số 11.

So sánh số 11 và số 15. Vì số 11 bé hơn số 15 nên bỏ đi nửa đầu danh sách.

Bước 2: Xét vị trí ở giữa của nửa sau danh sách, đó là vị trí của số 12.

So sánh số 12 và số 15. Vì số 12 bé hơn số 15 nên bỏ đi nửa đầu danh sách.

Bước 3: Xét vị trí ở giữa của nửa sau danh sách, đó là vị trí của số 25.

So sánh số 25 và số 15. Vì số 25 lớn hơn số 15 nên bỏ đi nửa sau danh sách.

Bước 4: Vì danh sách đã hết giá trị nên thông báo không tìm thấy số 15 trong danh sách. Thuật toán tìm kiếm kết thúc.

=> Cần thực hiện 4 bước lặp để thông báo không tìm thấy số 15 trong danh sách.

Câu 4: Cho danh sách sau:

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

Trả lời:

Bước 1: Xét vị trí ở giữa của dãy, đó là vị trí số 5

So sánh “Hoà” và “Mai”. Vì “H” đứng trước “M” trong bảng chữ cái nên bỏ đi nửa sau danh sách.

Bước 2: Xét vị trí ở giữa của nửa đầu của dãy là vị trí số 3

So sánh “Hòa” và “Hòa”, vì hai giá trị bằng nhau nên thuật toán kết thúc.

Sau 2 bước đã tìm thấy tên khách hàng tên “Hoà” nên thuật toán kết thúc.

Câu 5: Cho danh sách tên các nước sau đây:

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

1. 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.
2. b) Em hãy liệt kê các bước 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.

Trả lời:

1. a) Danh sách tên các nước theo thứ tự trong bảng chữ cái: Albania, Bolivia, Canada, Germany, Greenland, Iceland, Portugal, Scotland, Vietnam.
2. b) Các bước 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: Xét vị trí ở giữa của dãy, đó là vị trí thứ 5

So sánh “Greenland” và “Iceland” vì “G” đứng trước “I” trong bảng chữ cái nên bỏ đi nữa đầu danh sách.

Bước 2: Xét vị trí ở giữa của nữa sau của dãy, đó là vị trí thứ 7

So sánh Portugal và “Iceland” vì “P” đứng sau “I” trong bảng chữ cái nên bỏ đi nữa sau danh sách.

Bước 3: Xét vị trí ở giữa của dãy, đó là vị trí thứ 6

So sánh “Iceland” và “Iceland” vì hai giá trị bằng nhau nên thuật toán kết thúc.

Sau 3 bước đã tìm thấy tên nước “Iceland” nên thuật toán kết thúc.

Câu 6: Cho bảng điểm môn Tin học của học sinh tổ một như sau:

1. a) Em hãy sắp xếp lại danh sách theo thứ tự tăng dần của Điểm.
2. b) Em hãy liệt kê các bước lặp thực hiện thuật toán tìm kiếm nhị phân để tìm học sinh được điểm 9,5 môn Tin học. Hãy cho biết tên học sinh đó

Trả lời:

1. a) Dựa vào kiến thức đã học và thuật toán tìm kiếm nhị phân
2. b) Các bước thực hiện thuật toán tìm kiếm nhị phân để tìm học sinh được điểm 9,5 môn Tin học

Vùng tìm kiếm là dãy số: 7,5 8,0 8,5 9,0 9,5 10

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.

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.

IV. VẬN DỤNG CAO (2 CÂU)

Câu 1: Bài tập thực hành:

Em hay tìm kiếm thông tin trên internet để lập bảng danh sách khoảng 10 cuốn sách mà em yêu thích và đơn giá của mỗi cuốn sách. Sau đó thực hiện thuật toán tìm kiếm nhị phân để tìm cuốn sách mà em thích nhất trong danh sách vừa tìm được và cho biết đơn giá của cuốn sách đó.

Trả lời:

- Gợi ý cách làm:

Bước 1. Tìm kiếm thông tin trên Internet, lập bảng danh sách khoảng 10 cuốn sách đơn sách.

Bước 2. Sắp xếp tên sách theo thứ tự của bằng chữ cái.

Bước 3. Chỉ ra tên một cuốn sách mà em thích nhất.

Bước 4. Liệt kê các bước thực hiện thuật toán tìm kiếm nhị phân để tìm tên cuốn sách mà em thích nhất trong danh sách ở Bước 2.

Bước 5. Ghi ra đơn giá của cuốn sách tìm thấy ở Bước 4.

Các bước tìm kiếm tên sách “Tôi tự học” trong danh sách đã sắp xếp theo thuật toán tìm kiếm nhị phân:

Bước 1: Xét vị trí ở giữa của dãy, đó là vị trí thứ 5

So sánh”Hoàng tử bé” và “Tôi tự học” vì “H” đứng trước “T” trong bảng chữ cái nên bỏ đi nửa đầu danh sách

Bước 2: Xét vị trí ở giữa của nửa sau dãy, đó là vị trí thứ 8

So sánh “Tôi tự học” và “Tôi tự học” vì hai giá trị bằng nhau nên thuật toán kết thúc.

Sau 2 bước đã tìm thấy tên sách “Tôi tự học” với đơn giá sách là 80.000đ.

Câu 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:

- Gợi ý:

Ví dụ: Tìm tên một bạn trong danh sách lớp.

- Danh sách lớp, tên học sinh được sắp xếp theo thứ tự trong bảng chữ cái.

⇒ Để tìm tên một học sinh, chúng ta có thể thực hiện thuật toán tìm kiếm nhị phân để tìm kiếm.

- Hướng dẫn tìm tên bạn Nga, (giả sử trong lớp không có tên trùng nhau).

+ Chúng ta, xem xét từ vị trí giữa sách. So sánh tên cần tìm với tên ở vị trí xét.

Nếu kí tự đầu của tên đứng trước vần N thì tên cần tìm ở nửa sau danh sách.

Nếu kí tự đầu của tên đứng sau vần N thì tên cần tìm ở nửa trước của danh sách.

  Nếu tên trùng nhau thì dừng lại.

+ Nếu chưa tìm thấy thì tiếp tục tìm như bước trên.

+ Nếu tìm hết danh sách không có thì thông báo “Không tìm thấy”.