Bài giảng Cấu trúc dữ liệu và giải thuật chương 2: Định nghĩa tìm kiếm

CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT Chương II: Tìm kiếm Tìm kiếm Định nghĩa: Cho trước một phần tử Item và một dãy X có n phần tử x1, x2, …, xn có cùng kiểu dữ liệu. Tìm kiếm là xem Item có mặt trong dãy X hay không? (Tổng quát xem dãy X có phần tử nào thỏa một tính chất cho trước nào đó hay không) Phân loại: Tìm kiếm nội (internal searching) (nghiên cứu trong chương này) Tìm kiếm ngoại (external searching) Tùy theo dữ liệu đã được sắp xếp hay chưa mà ta có 2 phương pháp tìm kiếm: tuyến tính (tuần tự) và nhị phân Bài tóan: Input - Dãy X={x1, x2, …, xn} - Item: mục dữ liệu cần tìm. Trả về: trị 0 nếu không thấy Item trong X vị trí đầu tiên i trong X sao cho xi=Item Tìm tuần tự (sequential search) 5 Target key 7 13 5 21 6 2 8 15 position = 3 return 3 Số lần so sánh: 3 Tìm tuần tự - không tìm thấy 9 Target key 7 13 5 21 6 2 8 15 return 0 Số lần so sánh: 8 Tìm tuần tự - Mã C++ int sequential_search(mang x, int n, ElementType Item) { int Pos = 0; while(Pos<n && x[Pos]!=Item) Pos++; if (Pos==n) return 0; //Khong tim thay else return (Pos+1); } Tìm tuần tự - Đánh giá Số lần so sánh trên khóa đối với danh sách có n phần tử: Tìm không thành công: n. Tìm thành công, trường hợp tốt nhất: 1. Tìm thành công, trường hợp xấu nhất: n. Tìm thành công, trung bình: (n + 1)/2. Vậy: Ttn(n)=O(1), Ttb(n)=Txn(n)=O(n) Tìm trên mảng có thứ tự Dãy có thứ tự (ordered array): Phần tử tại vị trí i có khóa nhỏ hơn hoặc bằng phần tử tại vị trí j (i<j). Tìm tuần tự có thể kết thúc sớm hơn: Khi khóa cần tìm nhỏ hơn khóa của phần tử hiện tại. Cách tìm khác nhanh hơn: Tìm kiếm nhị phân !? Tìm nhị phân (binary search) Ý tưởng: So sánh khóa cần tìm với phần tử giữa. Nếu nó nhỏ hơn thì tìm bên trái dãy. Ngược lại tìm bên phải dãy. Lặp lại động tác này. Cần 2 chỉ mục top và bottom để giới hạn đoạn tìm kiếm trên danh sách. Khóa cần tìm nếu có chỉ nằm trong đoạn này. Tìm nhị phân 10 Target key 2 5 8 10 12 13 15 18 21 24 position = 4 return 4 Số lần so sánh: 3 Khóa cần tìm không bằng Khóa cần tìm nhỏ hơn Khóa cần tìm lớn hơn Khóa cần tìm bằng Tìm nhị phân int binary_search(mang x, ElementType Item, int n) { int bottom=0, top= n -1; while (bottom <= top) { int mid = (bottom + top)/2; if (Item == x[mid]) return (mid+1); else if(Item<x[mid]) top=mid-1; else bottom=mid+1; } return 0; } Tìm nhị phân Dựa trên ý tưởng tìm kiếm nhị phân viết giải thuật đệ quy (bài tập). Tìm nhị phân – Đánh giá Độ phức tạp của thuật tóan: Ttb(n) = Txn(n) = O(lg(n)) Ttn(n) = ?