Bài giảng Cấu trúc và dữ liệu giải thuật - Chương 7: Tìm kiếm - Phạm Thanh An

Nội dung text: Bài giảng Cấu trúc và dữ liệu giải thuật - Chương 7: Tìm kiếm - Phạm Thanh An

1. Chương 7: Tìm Kiếm Ths. Phạm Thanh An Bộ môn Khoa học máy tính - Khoa CNTT Trường Đại học Ngân hàng TP.HCM LOGO
2. Mục tiêu ❖Trình bày các thuật toán thông dụng cho việc tìm kiếm (Tìm tuần tự, tìm nhị phân) ❖Minh họa các thuật toán ❖Đánh giá thuật toán
3. Tầm quan trọng của tìm kiếm ❖Tìm kiếm một phần tử trong một tập hợp k đối tượng một thao tác thường sử dụng trong đời sống hằng ngày
4. Tầm quan trọng của tìm kiếm ❖Ví dụ: ▪ Cơ sở dữ liệu (Database): tìm 1 sinh viên, tìm 1 tài khoản ngân hàng, tài liệu, quyển sách. ▪ Internet: Yahoo!, Google,
5. TÌM KIẾM (SEARCHING) ❖ Định nghĩa ▪ Cho n bản ghi R1,R2, ,Rn, khóa tương ứng ki ▪ Hãy tìm bản ghi có giá trị khóa bằng X ❖ Kết quả tìm kiếm ▪ Thành công: có bản ghi với giá trị khóa X ▪ Không thành công: không có bản ghi thích hợp ❖ Phân loại tìm kiếm ▪ Tìm kiếm trong ▪ Tìm kiếm ngoài
6. Tìm kiếm tuần tự (sequential searching) ❖Ý tưởng ▪ Lần lượt tìm kiếm từ bản ghi đầu tiên cho đến khi tìm thấy, hoặc không còn phần tử để tìm kiếm ▪ Thực hiện tìm kiếm trên mảng / danh sách liên kết đơn
7. Tìm kiếm tuần tự (sequential searching) ❖Giải thuật bool SequentialSearch(int a[],int n,int x){ for (int i=0;i<n;i++){ if (a[i]==x) return true; } return false; }
8. Tìm kiếm tuần tự (sequential searching) ❖Độ phức tạp giải thuật ▪ Phép toán chính là phép so sánh ▪ Trường hợp tốt nhất: 1 phép so sánh ▪ Trường hợp xấu nhất: n phép so sánh ▪ Trường hợp trung bình: (n+1)/2 phép so sánh
9. Tìm kiếm nhị phân ❖ Ý tưởng ▪ Tiến hành trên dãy đã được sắp xếp tăng dần ▪ Dãy tìm kiếm a[1],a[2], ,a[n], khóa tìm kiếm X 1. So sánh khóa X với a[(n+1) div 2] 2. Nếu X=a[(n+1) div 2], kết thúc, ngược lại 1. Nếu X a[(n+1) div 2], quay lại (1), tìm kiếm trong dãy a[(n+1) div 2 + 1], ,a[n] 3. Kết thúc
10. Tìm kiếm nhị phân ▪ Giải thuật int BinarySearch(int a[ ],int l, int r,int x){ int m while (l a[m]) l=m+1; } return -1; }
11. Tìm kiếm nhị phân ❖ Giải thuật int BinarySearch1(int a[],int l,int r,int x) { int m=(l+r)/2; if (a[m]==x) return m; if ( x a[m]) return BinarySearch1(a,m+1,r,x); return -1; }