Đang chuẩn bị nút TẢI XUỐNG, xin hãy chờ
Tải xuống
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! | 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 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 3 Tì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 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 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 7 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
