Bài giảng "Cấu trúc dữ liệu và giải thuật trong C++ - Bài 13: Tìm kiếm - Search" cung cấp cho người học các kiến thức: Tìm kiếm tuần tự (Sequence search), tìm kiếm nhị phân (Binary search), bảng băm (Hash table). | Bài 13. Tìm kiếm- Search Bài toán Input Cho một tập S các phần tử mỗi phần tử là một bộ gồm khóa-giá trị key-value và một khóa k bất kỳ. Output Trong S có phần tử có khóa k hay không Search 1 Các phương pháp tìm kiếm Tìm kiếm tuần tự Sequence search Tìm kiếm nhị phân Binary search Bảng băm Hash table Search 2 1. Tìm kiếm tuần tự Tập S các phần tử được lưu bằng mảng hoặc danh sách liên kết. Thuật toán tìm kiếm Xuất phát từ phần tử đầu của dãy thực hiện so sánh khóa của nó với k. Nếu trùng nhau thì dừng lại nếu không trùng thì lặp lại với phần tử tiếp theo. Quá trình dừng lại khi tìm thấy hoặc không còn phần tử nào nữa gt Khi đó thông báo không tìm thấy. Search 3 1. Tìm kiếm tuần tự Ví dụ 1 Cho dãy S 0 45 3 34 13 7 43 9 11 Tìm xem trong dãy có phần tử k 33 Quá trình tìm kiếm 0 45 3 34 13 7 43 9 11 Bước 1 Bước 2 Bước 3 Bước 4 Bước 5 Bước 6 Bước 7 Bước 8 Bước 9 Không tìm thấy Search 4 1. Tìm kiếm tuần tự Ví dụ 2 Cho dãy S 0 45 3 34 13 7 43 9 11 Tìm xem trong dãy có phần tử k 13 Quá trình tìm kiếm 0 45 3 34 13 7 43 9 11 Bước 1 Bước 2 Bước 3 Bước 4 Bước 5 Tìm thấy tại vị trí 5 Search 5 1. Tìm kiếm tuần tự Thuật toán Input Cho một dãy S các phần tử mỗi phần tử là một bộ key và value. Một khóa k bất kỳ. Output Trong S có phần tử có khóa k hay không found 0 i 1 while chưa duyệt hết S amp amp found 0 if S i .key k found 1 i i 1 Chuyển sang phần tử kế tiếp return found Search 6 1. Tìm kiếm tuần tự Thời gian chạy Trong trường hợp xấu nhất thuật toán phải duyệt qua tất cả các phần tử của S. Vậy thời gian chạy là O n Search 7 2. Tìm kiếm nhị phân Tập S được tổ chức lưu trữ dựa trên mảng Tập S được tổ chức lưu trữ dạng cây nhị phân Search 8 Tìm kiếm nhị phân trên mảng Các phần tử của S được lưu trữ trong mảng và được sắp xếp theo thứ tự tăng dần giảm dần của giá trị khóa key . Thuật toán tìm kiếm nhị phân được thiết kế dựa trên chiến lược chia để trị Thuật toán So sánh khóa k với khóa của phần tử ở giữa dãy. Nếu trùng thì thông báo tìm thấy và dừng Nếu k gt thì gọi đệ qui .
