Lý thuyết Tin học 11 Bài 19 (Kết nối tri thức): Bài toán tìm kiếm

Lý thuyết Tin học 11 Bài 19: Bài toán tìm kiếm

A. Lý thuyết Bài toán tìm kiếm

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

- Bài toán 1: Miền dữ liệu là tất cả ảnh trên mạng Internet, kết quả là các ảnh hoa hồng.

- Bài toán 2: Miền dữ liệu là các tệp văn bản trên đĩa cứng, kết quả là tệp bai-hoc-1.docx.

- Bài toán 3: Miền dữ liệu là danh sách học sinh và điểm thi, kết quả là danh sách 5 bạn có điểm trung bình cao nhất.

2. Tìm kiếm tuần tự

- Cách An lật thẻ từ đầu đến cuối là tìm kiếm tuần tự trong dãy đối tượng.

- Bài toán tìm kiếm trên một dãy số: cho dãy A[0], A[1],..., A[n-1] và giá trị K, cần tìm chỉ số i mà A[i] = K, trả về -1 nếu không tìm thấy.

3. Tìm kiếm nhị phân

a. Phân tích bài toán

- Tìm kiếm nhị phân: tìm kiếm với dãy số đã được sắp xếp.

- Duyệt phần tử bất kì, xác định phần tử cần tìm ở bên trái hay bên phải.

- Quyết định tìm tiếp theo hướng nào mà không cần duyệt tất cả các phần tử của dãy số.

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

- Thuật toán tìm kiếm nhị phân thu hẹp phạm vi tìm kiếm liên tục.

- Nếu giá trị của phần tử ở giữa bằng K thì thông báo tìm thấy.

- Nếu K nhỏ hơn giá trị ở giữa, thu hẹp phạm vi tìm kiếm nửa đầu dãy tăng A (ngược lại thì phạm vi tìm kiếm nửa sau).

- Thiết lập left, right là chỉ số phần tử đầu và cuối của dãy cần tìm. Cần tìm K trong A[left..right].

- So sánh K với phần tử giữa dãy A[mid], có 3 trường hợp có thể xảy ra: 

+ Nếu K = A[mid] thì trả về chỉ số mid và kết thúc.

+ Nếu K < A[mid] thì phần tử cần tìm ở dãy con bên trái của A[mid], cập nhật right = mid - 1, giữ nguyên left.

+ Nếu K > A[mid] thì phần tử cần tìm ở dãy con bên phải của A[mid], cập nhật left = mid + 1, giữ nguyên right.

- Lặp lại cho đến khi tìm thấy hoặc phạm vi tìm kiếm bằng rỗng (right < left).

c. Minh hoạ các bước của thuật toán tìm kiếm nhị phân

- Tìm kiếm nhị phân nhanh hơn tìm kiếm tuần tự vì số phần tử cần duyệt giảm một nửa sau mỗi vòng lặp.

- Với cùng dãy số A và giá trị tìm kiếm K, thuật toán tìm kiếm tuần tự cần 6 bước, nhưng thuật toán tìm kiếm nhị phân chỉ cần 2 bước.

- Thuật toán tìm kiếm nhị phân trên dãy số đã sắp xếp tăng dần, hàm BinarySearch(A,K) trả lại chỉ số i nếu tìm thấy A[i] = K và -1 nếu không tìm thấy K trong dãy A.

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

Đang cập nhật…

Xem thêm các bài lý thuyết Tin học 11 sách Kết nối tri thức hay, chi tiết tại: 

Lý thuyết Bài 21: Các thuật toán sắp xếp đơn giản

Lý thuyết Bài 23: Kiểm thử và đánh giá chương trình

Lý thuyết Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Lý thuyết Bài 26: Phương pháp làm mịn dần trong thiết kế chương trình

Lý thuyết Bài 28: Thiết kế chương trình theo Mô đun