Xem mẫu
- 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 (𝑛)
nguon tai.lieu . vn
