L7- Bài 13: Thuật toán tìm kiếm

Thuật toán tìm kiếm tuần tự hoạt động như thế nào?

• Tìm kiếm bằng cách so sánh lần lượt từng phần tử trong danh sách.

• Chia danh sách thành hai phần và tìm kiếm trong từng phần.

• Sắp xếp danh sách theo thứ tự trước khi tìm kiếm.

• Loại bỏ các phần tử không cần thiết trước khi tìm kiếm.

Trong thuật toán tìm kiếm nhị phân, điều kiện gì cần thỏa mãn trước khi thực hiện tìm kiếm?

• Danh sách phải được sắp xếp.

• Danh sách không được có giá trị trùng lặp.

• Danh sách phải chứa số lượng phần tử chẵn.

• Danh sách phải chứa ít nhất 10 phần tử.

Thuật toán tìm kiếm nào thường nhanh hơn khi danh sách đã được sắp xếp?

• Tìm kiếm tuần tự

• Tìm kiếm ngẫu nhiên

• Tìm kiếm nhị phân

• Tìm kiếm toàn bộ

Tại sao thuật toán tìm kiếm nhị phân lại nhanh hơn tìm kiếm tuần tự trong danh sách sắp xếp?

• Vì nó kiểm tra tất cả các phần tử trong danh sách.

• Vì nó loại bỏ một nửa danh sách sau mỗi lần so sánh.

• Vì nó không cần sắp xếp danh sách trước.

• Vì nó chỉ tìm kiếm trong các phần tử ở giữa danh sách.

Giữa tìm kiếm và sắp xếp có mối liên hệ gì?

• Tìm kiếm yêu cầu danh sách phải được sắp xếp để tăng hiệu quả.

• Sắp xếp không ảnh hưởng đến kết quả tìm kiếm.

• Tìm kiếm làm danh sách trở nên sắp xếp tự động.

• Danh sách chỉ cần sắp xếp khi sử dụng thuật toán tuần tự.

Cho danh sách số: [2, 5, 8, 10, 15]. Nếu dùng thuật toán tìm kiếm nhị phân để tìm số 8, số lần so sánh tối đa cần thực hiện là:

• 1

• 2

• 3

• 5

Một danh sách chưa sắp xếp: [12, 4, 8, 10, 6]. Em cần thực hiện tìm kiếm nhị phân trên danh sách này. Bước đầu tiên cần làm là gì?

• Tìm kiếm số cần tìm ngay.

• Sắp xếp danh sách theo thứ tự tăng dần.

• Tìm số lớn nhất trong danh sách.

• Loại bỏ các phần tử không cần thiết.

Em cần tìm số 18 trong danh sách sắp xếp: [5, 10, 15, 20, 25, 30] bằng thuật toán tìm kiếm nhị phân. Mô phỏng các bước tìm kiếm:

• So sánh với 15 -> loại bỏ [5, 10] -> so sánh với 20 -> loại bỏ [25, 30] -> tìm thấy 18.

• So sánh với 15 -> loại bỏ [20, 25, 30] -> so sánh với 10 -> tìm thấy 18.

• So sánh với 15 -> loại bỏ [20, 25, 30] -> so sánh với 10 -> loại bỏ [5] -> không tìm thấy 18.

• So sánh với 15 -> loại bỏ [5, 10] -> so sánh với 20 -> tìm thấy 18.