Bài toán tìm kiếm SVIP

1. Bài toán tìm kiếm trong thực tế

Một số kiến thức cần ghi nhớ:

• Tìm kiếm là một trong những bài toán quan trọng nhất của Tin học.
• Việc thiết kế thuật toán tìm kiếm phụ thuộc vào cấu trúc của miền dữ liệu cần tìm kiếm và tiêu chí cụ thể của bài toán tìm kiếm. 
• Kết quả tìm kiếm của bài toán có thể tồn tại một hoặc nhiều kết quả, hoặc là không tồn tại kết quả.

Một số ví dụ về miền dữ liệu và kết quả của các bài toán tìm kiếm trong thực tế:

• Bài toán 1: Em cần tìm hình ảnh bông hoa hồng trên Internet để đưa vào bài thuyết trình.
• Bài toán 2: Em cần tìm tệp dữ liệu (tệp văn bản) lưu trữ lâu ngày trong máy tính cá nhân.
• Bài toán 3: GV cần tìm ra HS có điểm thi Toán cao nhất trong kỳ thi Olympic Toán.
• Bài toán 4: Xác định tên con đường từ nhà đến trường thông qua phần mềm bản đồ số.

2. Bài toán tìm kiếm trong lập trình

Đề bài: Cho dãy A[0], A[1],..., A[n-1], hãy tìm kiếm phần tử có giá trị là K.

• Đầu vào: Dãy A có n phần tử và giá trị K.
• Đầu ra: Tìm thấy ➜ trả ra vị trí i, ngược lại ➜ trả ra -1.

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

Minh họa thuật toán với dãy số cụ thể

Xét dãy A = [1, 4, 7, 8, 3, 9, 10] và giá trị K = 9. Quá trình thực hiện thuật toán được mô phỏng như sau.

Cài đặt thuật toán bằng ngôn ngữ Python

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

Phân tích bài toán tìm kiếm trên dãy đã sắp xếp

Dãy A là dãy đã sắp xếp theo thứ tự xác định (tăng dần hoặc giảm dần), ta có tính chất: "Có thể xác định phần tử K nằm ở bên trái hay bên phải phần tử A[i] đang xét."

Sơ đồ thuật toán tìm kiếm nhị phân

Minh họa thuật toán tìm kiếm nhị phân

Xét dãy A = [1, 3, 4, 7, 8, 9, 10] và giá trị K = 9. Qúa trình thực hiện thuật toán được mô phỏng như sau.

 Cài đặt thuật toán bằng ngôn ngữ Python

Tổng kết kiến thức

1. Thiết kế thuật toán tìm kiếm phụ thuộc vào cấu trúc của miền dữ liệu cần tìm kiếm và tiêu chí cụ thể của bài toán tìm kiếm. 

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

• Phù hợp cho các bài toán tìm kiếm với dữ liệu chưa được sắp xếp.
• Thực hiện bằng cách duyệt lần lượt các phần tử trong dãy.

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

• Phù hợp cho các bài toán tìm kiếm với dữ liệu đã được sắp xếp.
• Thực hiện bằng cách lặp hành động: chia dãy đang xét thành hai nửa và xác định phạm vi tìm kiếm ở nửa nào trên dãy dựa trên giá trị cần tìm.