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

Tóm tắt Lý thuyết Tin học 11 Kết nối tri thức Bài 19: Bài toán tìm kiếm theo chương trình Sách mới ngắn gọn nhất. Tổng hợp lý thuyết Tin học 11 trọn bộ chi tiết, đầy đủ.

Bài 19: Bài toán tìm kiếm

- Soạn Tin học 11 Kết nối tri thức Bài 19

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.

>>> Xem toàn bộ: 

- Lý thuyết Tin học 11 Kết nối tri thức

- Soạn Tin 11 Kết nối tri thức

- Sơ đồ tư duy Tin học 11 Kết nối tri thức

- Trắc nghiệm Tin 11 Kết nối tri thức

-------------------------------------------

Trên đây Toploigiai đã cùng các bạn Tóm tắt Lý thuyết Tin học 11 Kết nối tri thức Bài 19: Bài toán tìm kiếm theo chương trình Sách mới ngắn gọn nhất. Mời các bạn hãy click ngay vào trang chủ Top lời giải để tham khảo và chuẩn bị bài cho năm học mới Lớp 11 nhé. Chúc các bạn học tốt.