Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 7: Tìm kiếm - Nguyễn Thị Khiêm Hòa

Chương 7: Tìm kiếm Giảng viên: Ths. Nguyễn Thị Khiêm Hòa Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 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 Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 2 Đặt vấn đề  Tìm kiếm một phần tử có khóa x trong một tập hợp là thao tác thường gặp trong đời sống hàng ngày.  Ví dụ:  Tìm trong cơ sở dữ liệu: tài khoản ngân hàng, thông tin sinh viên,  Search Engine: Yahoo, Google, Bing Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 3 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 Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 4 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 dữ liệu thỏa điều kiện tìm kiếm, 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 Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 5 Tìm kiếm tuần tự (sequential searching)  Cài đặt public int Linear_Search(int x) { int i = 0; while(i < idx) { if(A[i] != x) i++; return i; } return -1; } Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 6 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 Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 7 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  Tìm trên dãy A phần tử có khóa X:  Chọn phần tử giữa có giá trị k  Nếu X < k: tìm trên dãy các phần tử đứng trước k  Nếu X > k: tìm trên dãy các phần tử đứng sau k  Nếu X = k: tìm thấy.  Lặp lại các bước trên cho đến khi tìm thấy hoặc dãy không còn phần tử để tìm kiếm. Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 8 Tìm kiếm nhị phân public int Bin_Search(int x) { int left =0; int right = idx - 1; while (left < right) { int k = (left + right) / 2; if (A[k] < x) left = k + 1; else if (A[k] > x) right = k - 1; else return k; } return -1; } Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 9 Bài tập Thực hiện Cài đặt phương thức tìm nhị phân bằng phương pháp đệ quy. 20 min Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 10 Tìm kiếm nhị phân  Phương pháp tìm nhị phân hạn chế được không gian tìm kiếm  Độ 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: log2n phép so sánh, nhỏ hơn n/2 rất nhiều.  Trường hợp trung bình: log2n phép so sánh Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 11 Tìm kiếm nhị phân  Tuy nhiên phương pháp tìm nhị phân chỉ thực hiện được trên dãy đã sắp xếp. Do đó cần tính chi phí sắp xếp vào thuật toán này. Nếu dãy biến động liên tục thì chi phí này không hề nhỏ. Cây nhị phân tìm kiếm là giải pháp trong trường hợp này Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 12 Q&A Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 13