Bài giảng Cấu trúc dữ liệu: Tìm kiếm - TS. Lê Minh Trung & Th.S Lương Trần Ngọc Khiết

Bài giảng Cấu trúc dữ liệu: Chương 2 Tìm kiếm cung cấp cho người học những kiến thức như: 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. Mời các bạn cùng tham khảo!
Nội dung trích xuất từ tài liệu:
Bài giảng Cấu trúc dữ liệu: Tìm kiếm - TS. Lê Minh Trung & Th.S Lương Trần Ngọc Khiết TS. Lê Minh Trung ThS Lương Trần Ngọc KhiếtKhoa CNTT, Đại học Sư phạm, TP. HCMNộ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ânKhá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; iTìm tuần tự (sequential search) position = 2 5 Target key 0 1 2 3 4 5 6 7 7 13 5 21 6 2 8 15 return success Số lần so sánh: 3Tìm tuần tự - không tìm thấy 9 Target key 0 1 2 3 4 5 6 7 7 13 5 21 6 2 8 15 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 ?−1 1 ? ?(?+1) ?+1  ?? = ?=0 ? + 1 ? ??? = ? ? = ?=1 ? = = = ?(?) ? 2? 2Tì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ấyint BinarySearch(int a[], int n, int key){ int left=0, right=n-1,middle; while(leftTìm nhị phân position = 3 10 Khóa cần tìm bằng không nhỏ lớn hơn hơn bằng Target key 0 1 2 3 4 5 6 7 8 9 2 5 8 10 12 13 15 18 21 24 left middle right return success Số lần so sánh: 7Phâ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 (?)