Bài giảng Cấu trúc dữ liệu - Chương 2: Tìm kiếm - Lê Minh Trung

TS. Lê Minh Trung ThS Lương Trần Ngọc Khiết Khoa CNTT, Đại học Sư phạm, TP. HCM Nội dung  Giới thiệu bài toán tìm kiếm  Tìm kiếm tuần tự  Tìm kiếm nhị phân Khái niệm tìm kiếm  Cho biết:  Một danh sách các bản ghi (record).  Một khóa cần tìm.  Tìm bản ghi có khóa trùng với khóa cần tìm (nếu có).  Đo độ hiệu quả:  Số lần so sánh khóa cần tìm và khóa của các bản ghi  Phân loại:  Tìm kiếm nội (internal searching)  Tìm kiếm ngoại (external searching) Tìm kiếm tuần tự  Input: mảng đầu vào int a[n], khóa cần tìm key  Output: vị trí tìm thấy đầu tiên của key trong mảng hoặc -1 nếu không tìm thấy int SequentialSearch(int a[n], int key) { for(int i=0; i<n; i++)if(a[i]==key)break; if(i<n)return i; return -1; } Tìm tuần tự (sequential search) 5 Target key 7 13 5 21 6 2 8 15 0 1 2 3 4 5 6 7 position = 2 return success 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 0 1 2 3 4 5 6 7 return not_present Số lần so sánh: 8 Phân tích tìm kiếm tuần tự  Không tìm thấy:  Số phép so sánh: SS=n  Tìm thấy:  Tốt nhất (a[0]=key): SS=1  Xấu nhất (a[n-1]=key): SS=n  Trung bình  𝑆𝑆 = 𝑖=0 𝑛−1 𝑖 + 1 𝑃 𝑘𝑒𝑦 = 𝑎 𝑖 = 1 𝑛 𝑖=1 𝑛 𝑖 = 𝑛(𝑛+1) 2𝑛 = 𝑛+1 2 = 𝑂(𝑛) Tìm kiếm nhị phân  Dùng trong trường hợp mảng đầu vào đã được sắp thứ tự  Ý 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 mảng.  Ngược lại tìm bên phải mảng.  Lặp lại động tác này.  Cần 2 chỉ mục left và right để giới hạn đoạn tìm kiếm trên mảng.  Khóa cần tìm nếu có chỉ nằm trong đoạn này. Tìm kiếm nhị phân  Input: mảng tăng int a[n], khóa cần tìm key  Output: vị trí tìm thấy đầu tiên của key trong mảng hoặc -1 nếu không tìm thấy int BinarySearch(int a[], int n, int key){ int left=0, right=n-1,middle; while(left<=right){ middle = (left+right)/2; if(a[middle]==key)return middle; if(key<a[middle])right=middle-1; else left=middle+1; } return -1; } Tìm nhị phân 10 Target key 2 5 8 10 12 13 15 18 21 24 0 1 2 3 4 5 6 7 8 9 left rightmiddle position = 3 return success Số lần so sánh: 7 Khóa cần tìm không bằngn ỏ hơnlớn bằ g Phân tích tìm kiếm nhị phân  Số lần lặp không vượt quá 𝑙𝑜𝑔2𝑛  Trong mỗi vòng lặp sử dụng tối đa hai phép so sánh  Số phép so sánh tối đa 2 𝑙𝑜𝑔2𝑛  Độ phức tạp của thuật toán: 𝑂 𝑙𝑜𝑔2(𝑛)