Giải bài 2 Tìm kiếm nhị phân

Cách tra cứu, tìm giải nghĩa một từ trong từ điển:

• Bước 1: Xác định từ cần tìm là gì. Ví dụ, chúng ta muốn tìm từ "hat".
• Bước 2: Chia đổi cuốn từ điển thành 2 phần bằng nhau, chọn 1 từ bất kì nằm ở giữa cuốn từ điển. Ví dụ, chọn từ "mother". Vì cuốn từ điển sắp xếp theo bảng chữ cái nên chữ h sẽ đứng trước chữ m, vậy tiếp theo ta chỉ cần tìm trong nửa đầu của cuốn từ điển.
• Bước 3: Ta lại tiếp tục chia đổi nửa đầu cuốn từ điển và thực hiện tương tự như bước 2. Chọn một từ nằm ở giữa, ví dụ là từ "go". Vì chữ g đứng trước chữ h nên phạm vi tìm kiếm sẽ từ chữ "go" cho đến chữ "mother".
• Bước 4: Chúng ta tiếp tục chia đôi phạm vi từ chữ "go" cho đến chữ "mother" và thực hiện tương tự bước 3 cho đến khi ta tìm được từ "hat" thì ta kết thúc việc tìm kiếm.

Cách tìm trên có thể gọi là áp dụng thuật toán tìm kiếm nhị phân.

TỰ KIỂM TRA

Câu 1. Hãy mô tả quy trình chia đổi dần để thực hiện tìm kiếm nhị phân.

Câu 2. Theo em, có phải với bất cứ dãy số nào cũng có thể áp dụng được thuật toán tìm kiếm nhị phân không? Giải thích tại sao.

Câu trả lời: