Tin học 7 Bài 2: Tìm kiếm nhị phân Tin học lớp 7 trang 81 sách Cánh diều

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.

Câu 1. Quy trình chia đổi dần để thực hiện tìm kiếm nhị phân là:

Gọi số cần tìm kiếm là x, gọi dãy số đã sắp thứ tự là a₁ cho đến a_n.

Bước 1: Chia dãy thành 2 phần bằng nhau và so sánh giá trị cần tìm với giá trị nằm giữa 2 phần đó (gọi là a_n/2). Có thể xảy ra hai trường hợp:

• Nếu giá trị cần tìm lớn hơn (x > a_n/2), ta xét nửa sau của dãy (từ a_n/2 đến a_n).
• Nếu giá trị cần tìm nhỏ hơn (x < a_n/2), thực hiện xét nửa trước của dãy (từ a₁ đến a_n/2).

Bước 2: Sau đó, ta xét lại phạm vi tìm kiếm phù hợp. Nếu x = a_n/2, ta xác định được vị trí của số cần tìm và kết thúc tìm kiếm.

Bước 3: Tiếp tục thực hiện 2 bước trên cho đến khi tìm được giá trị cần tìm. Nếu không tìm được x ta suy ra trong dãy không tồn tại số có giá trị như đề bài yêu cầu.

Câu 2. Không 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 vì chỉ có dãy số có thứ tự thì mới chia đôi và xác định phạm vi tìm kiếm để tìm ra kết quả chính xác được, còn dãy không có thứ tự thì không thể áp dụng thuật toán tìm kiếm nhị phân.