Bài 13. Thuật toán tìm kiếm SVIP

1. Thuật toán tìm kiếm tuần tự

⚡ Bài toán 1. Tìm số điện thoại trong danh bạ được mô tả như sau:

• Đầu vào: Dãy số (được ghi trên các thẻ) và số cần tìm.
• Đầu ra: Thông báo vị trí tìm thấy hoặc thông báo không tìm thấy số cần tìm.

📝Thuật toán. Duyệt lần lượt từng số trong dãy số từ đầu đến cuối, với mỗi thẻ số em thực hiện lật và kiểm tra xem số ghi trên thẻ có đúng với số cần tìm không, nếu đúng thì thông báo vị trí tìm thấy và kết thúc việc tìm kiếm, nếu không thì chuyển sang thẻ tiếp theo. Nếu đã lật hết các thẻ mà không tìm thấy số cần tìm thì thông báo không tìm thấy và kết thúc việc tìm kiếm.

2. Thuật toán tìm kiếm nhị phân

⚡ Bài toán 2. Tìm số điện thoại trong danh bạ được mô tả như sau:

• Đầu vào: Dãy số (được ghi trên các thẻ) theo chiều không giảm và số cần tìm.
• Đầu ra: Thông báo vị trí tìm thấy hoặc thông báo không tìm thấy số cần tìm.

📝Thuật toán. Áp dụng với dãy giá trị đã được sắp xếp không giảm (hoặc không tăng):

Bước 1. So sánh giá trị cần tìm với giá trị của phần tử giữa dãy đang xét. Thẻ số ở giữa dãy có số thứ tự là phần nguyên của phép chia: (Số lượng thẻ của dãy + 1)/2.

Bước 2. Nếu bằng nhau thì thông báo vị trí tìm thấy và kết thúc.

Bước 3. Nếu nhỏ hơn thì xét dãy ở nửa trước (hoặc nửa sau), nếu lớn hơn thì xét dãy ở nửa sau (hoặc nửa trước).

Bước 4. Nếu dãy rỗng thì thông báo không tìm thấy và kết thúc tìm kiếm, ngược lại thì quay về Bước 1 cho đến khi dãy chỉ còn một thẻ số thì nửa trước (hoặc nửa sau) là dãy rỗng (dãy không có thẻ số nào).