Bạn Minh có danh bạ điện thoại ghi tên và số điện thoại của 30 người thân/bạn bè (danh

Câu hỏi số 990938:

Vận dụng

Bạn Minh có danh bạ điện thoại ghi tên và số điện thoại của 30 người thân/bạn bè (danh sách được sắp xếp theo thứ tự ABC của Tên). Minh muốn tìm số điện thoại của người bạn tên là Thắng.

a) Minh nên sử dụng thuật toán tìm kiếm tuần tự hay tìm kiếm nhị phân? Giải thích tại sao (Nêu ít nhất 2 lý do)?

b) Giả sử Minh sử dụng thuật toán nhị phân, hãy mô tả ba bước đầu tiên Minh thực hiện để tìm kiếm (chỉ ra vị trí bắt đầu, vị trí giữa, và khu vực tìm kiếm tiếp theo).

Quảng cáo

Xem lời giải

Câu hỏi:990938

Phương pháp giải

Vận dụng kiến thức về thuật toán tìm kiếm tuần tự và tìm kiếm nhị phân.

- Tìm kiếm tuần tự: Kiểm tra lần lượt từng phần tử từ đầu danh sách đến khi tìm thấy hoặc hết danh sách.

- Tìm kiếm nhị phân: So sánh phần tử cần tìm với phần tử ở giữa danh sách, sau đó loại bỏ một nửa phạm vi tìm kiếm.

Giải chi tiết

a) Minh nên sử dụng thuật toán tìm kiếm nhị phân vì:

- Danh sách 30 người đã được sắp xếp theo thứ tự ABC nên đáp ứng điều kiện áp dụng thuật toán tìm kiếm nhị phân.

- Mỗi lần so sánh, thuật toán có thể loại bỏ một nửa phạm vi tìm kiếm, giúp giảm số lần so sánh và tìm kiếm nhanh hơn so với tìm kiếm tuần tự khi danh sách đủ lớn.

b) Mô tả ba bước đầu tiên: Giả sử danh sách được đánh số thứ tự từ 1 đến 30.

Bước 1: Bắt đầu tìm kiếm. Vị trí giữa là $\dfrac{30}{2} = 15$ (hoặc 16). So sánh Thắng với tên bạn ở vị trí thứ 15 (hoặc 16).

Bước 2: Dựa trên kết quả so sánh, loại bỏ nửa danh sách không chứa Thắng. Ví dụ: Nếu Thắng lớn hơn tên ở vị trí 15, khu vực tìm kiếm tiếp theo là từ vị trí 16 đến 30 (15 người).

Bước 3: Xác định vị trí giữa của khu vực mới tìm kiếm (ví dụ: vị trí giữa của 16-30 là vị trí thứ 23). So sánh Thắng với tên bạn ở vị trí 23. (Tiếp tục loại bỏ nửa không cần thiết).

Group 2K8 ôn Thi ĐGNL & ĐGTD Miễn Phí

Câu hỏi trước Câu tiếp theo

>> 2K9 Chú ý! Lộ Trình Sun 2027 - 1 lộ trình ôn đa kỳ thi (TN THPT, ĐGNL (Hà Nội/ Hồ Chí Minh), ĐGNL Sư Phạm, ĐGTD, ĐGNL Bộ Công an, ĐGNL Bộ Quốc phòng- Click xem ngay) tại Tuyensinh247.com. Cập nhật bám sát bộ SGK mới, Thầy Cô giáo giỏi, 3 bước chi tiết: Nền tảng lớp 12; Luyện thi chuyên sâu; Luyện đề đủ dạng đáp ứng mọi kì thi.