Trang chủ Lớp 11 Tin học lớp 11 SGK Tin học 11 - Kết nối tri thức (?) Câu hỏi mục III Hoạt động 3 Bài 19 (trang 89)...

(?) Câu hỏi mục III Hoạt động 3 Bài 19 (trang 89) Tin học 11: Cho trước một dãy số đã được sắp xếp theo thứ tự tăng dần. Hãy đọc

Giải (?) Câu hỏi mục III Hoạt động 3 Bài 19. Bài toán tìm kiếm (trang 89) – SGK Tin học 11 Kết nối tri thức. Gợi ý: Vận dụng kiến thức mục 3 trang 91 SGK để trả lời câu hỏi.

Câu hỏi/Đề bài:

Cho trước một dãy số đã được sắp xếp theo thứ tự tăng dần. Hãy đọc, quan sát và thảo luận cách làm sau đây để hiểu được thuật toán tìm kiếm nhị phân, biết được tính ưu việt của thuật toán này so với thuật toán tìm kiếm tuần tự trên một dây các phần từ đã sắp xếp.

Lời giải:

Thuật toán tìm kiếm nhị phân thực hiện tìm kiếm một mảng đã sắp xếp bằng cách liên tục chia các khoảng tìm kiếm thành 1 nửa. Bắt đầu với một khoảng từ phần tử đầu mảng, tới cuối mảng. Nếu giá trị của phần tử cần tìm nhỏ hơn giá trị của phần từ nằm ở giữa khoảng thì thu hẹp phạm vi tìm kiếm từ đầu mảng tới giữa mảng và ngược lại. Cứ thế tiếp tục chia phạm vi thành các nửa cho đến khi tìm thấy hoặc đã duyệt hết.

Thuật toán tìm kiếm nhị phân tỏ ra tối ưu hơn so với tìm kiếm tuyến tính ở các mảng có độ dài lớn và đã được sắp xếp. Ngược lại, tìm kiếm tuyến tính sẽ tỏ ra hiệu quả hơn khi triển khai trên các mảng nhỏ và chưa được sắp xếp.