Bài 7. Lập trình giải bài toán tìm kiếm SVIP

1. Bài toán tìm kiếm

a) Khái niệm bài toán tìm kiếm

Cho một yêu cầu tìm kiếm và một tập hợp dữ liệu là phạm vi tìm kiếm. Hãy tìm mục (các mục) dữ liệu đáp ứng yêu cầu tìm kiếm đã cho hoặc khẳng định không có mục dữ liệu nào đáp ứng yêu cầu đó.

b) Tìm kiếm tuần tự bằng hàm của Python

Phương thức index thực hiện tìm kiếm phần tử x trong một dãy tuần tự (xâu kí tự, mảng hoặc danh sách) và trả về:

• Nếu xuất hiện nhiều lần thì đưa ra chỉ số của lần xuất hiện đầu tiên.
• Báo lỗi “ValueError” nếu không tìm thấy.
• Phương thức index có hai tham số tuỳ chọn: lo, hi để hạn chế thực hiện tìm kiếm chỉ trong đoạn con của dãy số, bắt đầu từ chỉ số lo (lowest) và kết thúc ở hi(highest).

Cú pháp: dãy_số.index(giá_trị, lo, hi)

⚡Ví dụ. Với mảng a = [1, 2, 3, 4, 5, 6], câu lệnh print(a.index(3,1,4)) sẽ in ra màn hình kết quả là 2, cho biết vị trí của phần tử 3 trong đoạn [1, 4] ở mảng a.

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

Chi tiết dần từng bước thuật toán tìm kiếm tuần tự được liệt kê như sau:

Trong mô tả trên có một số cụm từ như: “Số đang xét là số ở đầu dãy”, “Chưa hết dãy số”, “Chuyển đến xét số tiếp theo trong dãy”, “Thông báo vị trí tìm thấy x và kết thúc”, “Thông báo không tìm thấy x và kết thúc”. Dưới đây là kết quả thay thế những cụm từ trên bằng mã giả.

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

Hướng dẫn viết mã giả của thuật toán tìm kiếm nhị phân

• Xác định các cụm từ cần làm chi tiết hơn bằng mã giả: “Phạm vi tìm kiếm là dãy ban đầu”; “Vẫn còn phạm vi tìm kiếm”; “Xác định phần tử a_m, ở giữa phạm vi tìm kiếm”, “Loại bỏ nửa dãy chắc chắn không chứa x”, “Phạm vi tìm kiếm là nửa dãy còn lại”, “Thông báo không tìm thấy x và kết thúc”.
• Bổ sung thêm lo là chỉ số phần tử ở đầu trái đoạn con và hi là chỉ số phần tử ở đầu phải đoạn con.
• Công thức tính chỉ số m của phần tử ở “giữa” đoạn con là (lo + hi)/2, kết quả đảm bảo là số nguyên.