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

Chia sẻ: Conbongungoc09 | Ngày: | Loại File: PDF | Số trang:11

Thêm vào BST

Báo xấu

11
lượt xem 2
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

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!

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: 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ế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
Tì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(left
Tì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 (𝑛)