Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 2: Tìm kiếm

hung
1
C
Ấ
U
 T
R
Ú
C
 D
Ữ
LI
Ệ
U
 V
À
G
IẢ
I T
H
U
Ậ
T
1
CHƯƠNG 2
TÌM KIẾM
C
Ấ
U
 T
R
Ú
C
 D
Ữ
LI
Ệ
U
 V
À
G
IẢ
I T
H
U
Ậ
T
2
Nội Dung
¾ Các giải thuật tìm kiếm nội
1. Tìm kiếm tuyến tính
2. Tìm kiếm nhị phân
C
Ấ
U
 T
R
Ú
C
 D
Ữ
LI
Ệ
U
 V
À
G
IẢ
I T
H
U
Ậ
T
3
Bài Toán Tìm Kiếm
¾ Cho danh sách có n phần tử a0, a1, a2…, an-1. 
¾ Để đơn giản trong việc trình bày giải thuật ta dùng
mảng 1 chiều a để lưu danh sách các phần tử nói
trên trong bộ nhớ chính.
¾ Tìm phần tử có khoá bằng X trong mảng
ƒ Giải thuật tìm kiếm tuyến tính (tìm tuần tự)
ƒ Giải thuật tìm kiếm nhị phân
™ Lưu ý: Trong quá trình trình bày thuật giải ta dùng
ngôn ngữ lập trình C.
hung
2
C
Ấ
U
 T
R
Ú
C
 D
Ữ
LI
Ệ
U
 V
À
G
IẢ
I T
H
U
Ậ
T
4
Tìm Kiếm Tuyến Tính
¾ Ý tưởng : So sánh X lần lượt với phần tử thứ 1, 
thứ 2,…của mảng a cho đến khi gặp được khóa
cần tìm, hoặc tìm hết mảng mà không thấy.
¾ Các bước tiến hành
• Bước 1: Khởi gán i=0;
• Bước 2: So sánh a[i] với giá trị x cần tìm, có 2 khả năng
+ a[i] == x tìm thấy x. Dừng;
+ a[i] != x sang bước 3;
• Bước 3: i=i+1 // Xét tiếp phần tử kế tiếp trong mảng
Nếu i==N: Hết mảng. Dừng;
Ngược lại: Lặp lại bước 2;
C
Ấ
U
 T
R
Ú
C
 D
Ữ
LI
Ệ
U
 V
À
G
IẢ
I T
H
U
Ậ
T
5
Minh Họa Thuật Toán Tìm Kiếm Tuyến Tính
1 2 3 4 5 60
2 8 5 1 6 4 6
X=6
i
Tìm thấy 6 tại vị trí 4
C
Ấ
U
 T
R
Ú
C
 D
Ữ
LI
Ệ
U
 V
À
G
IẢ
I T
H
U
Ậ
T
6
Minh Họa Thuật Toán Tìm Kiếm Tuyến Tính (tt)
1 2 3 4 5 60
2 8 5 1 6 4 6
X=10
i
i=7, không tìm thấy
hung
3
C
Ấ
U
 T
R
Ú
C
 D
Ữ
LI
Ệ
U
 V
À
G
IẢ
I T
H
U
Ậ
T
7
Thuật Toán Tìm Kiếm Tuyến Tính
¾ Hàm trả về 1 nếu tìm thấy, ngược lại trả về 0:
int LinearSearch(int a[],int n, int x)
{
int i=0;
while((i<n)&&(a[i]!=x)) 
i++;
if(i==n)
return -1; //Tìm không thấy x
else
return i; //Tìm thấy
}
C
Ấ
U
 T
R
Ú
C
 D
Ữ
LI
Ệ
U
 V
À
G
IẢ
I T
H
U
Ậ
T
8
Ðánh Giá Thuật Toán Tìm Tuyến Tính
Trường hợp Css
Xấu nhất
Trung bình
N 
(N+1) / 2
¾ Độ phức tạp O(N)
Tốt nhất 1 
C
Ấ
U
 T
R
Ú
C
 D
Ữ
LI
Ệ
U
 V
À
G
IẢ
I T
H
U
Ậ
T
9
Cải Tiến Thuật Toán Tìm Tuyến Tính
¾ Nhận xét: 
ª Số phép so sánh của thuật toán trong
trường hợp xấu nhất là 2*n.
¾ Cải tiến:
ªĐể giảm thiểu số phép so sánh trong vòng
lặp cho thuật toán, ta thêm phần tử “lính
canh” vào cuối dãy.
hung
4
C
Ấ
U
 T
R
Ú
C
 D
Ữ
LI
Ệ
U
 V
À
G
IẢ
I T
H
U
Ậ
T
10
107 5 12 41 10 32 13 9 15 3
0 1 2 3 4 5 6 7 8 9
10
7 5 12 41 10 32 13 9 15 3
0 2 3 4 5 6 7 8 9 10
25
11
25
¾Minh họa tìm x =10
¾Minh họa tìm x = 25
C
Ấ
U
 T
R
Ú
C
 D
Ữ
LI
Ệ
U
 V
À
G
IẢ
I T
H
U
Ậ
T
11
Cải Tiến Thuật Toán Tìm Tuyến Tính
int LinearSearch2(int a[],int n, int x)
{ int i=0; 
a[n]=x; // a[n] là phần tử “lính canh”
while(a[i]!=x) 
i++;
if(i==n)
return -1; // Tìm không thấy x
else
return 0; // Tìm thấy
}
C
Ấ
U
 T
R
Ú
C
 D
Ữ
LI
Ệ
U
 V
À
G
IẢ
I T
H
U
Ậ
T
12
Thuật Toán Tìm Kiếm Nhị Phân
¾ Được áp dụng trên mảng đã có thứ tự.
¾ Ý tưởng:
ƒ Giả xử ta xét mảng có thứ tự tăng, khi ấy ta có ai-1<ai<ai+1
ƒ Nếu X>ai thì X chỉ có thể xuất hiện trong đoạn [ai+1, an-1]
ƒ Nếu X<ai thì X chỉ có thể xuất hiện trong đoạn [a0, ai-1]
ƒ Ý tưởng của giải thuật là tại mỗi bước ta so sánh X với
phần tử đứng giữa trong dãy tìm kiếm hiện hành, dựa vào
kết quả so sánh này mà ta quyết định giới hạn dãy tìm kiếm
ở nữa dưới hay nữa trên của dãy tìm kiếm hiện hành.
hung
5
C
Ấ
U
 T
R
Ú
C
 D
Ữ
LI
Ệ
U
 V
À
G
IẢ
I T
H
U
Ậ
T
13
Minh Họa Thuật Toán Tìm Nhị Phân
1 2 4 6 9 10
X=2
L
Tìm thấy 2 tại vị trí 1
7
1 2 3 4 5 60
RM
C
Ấ
U
 T
R
Ú
C
 D
Ữ
LI
Ệ
U
 V
À
G
IẢ
I T
H
U
Ậ
T
14
3 14 16 19 22 41 46 51 63 71
1 2 3 4 5 6 7 8 9 10
x
ml m
x
r
m
x
Tìm thấy x tại 
vị trí 6
Minh họa tìm x = 41
C
Ấ
U
 T
R
Ú
C
 D
Ữ
LI
Ệ
U
 V
À
G
IẢ
I T
H
U
Ậ
T
15
3 14 16 19 22 41 46 51 63 71
0 1 2 3 4 5 6 7 8 9
x
m m
x
0
r
m
x
l
m
x
l > r: Kết thúc: 
Không tìm thấy
Minh họa tìm x = 45
hung
6
C
Ấ
U
 T
R
Ú
C
 D
Ữ
LI
Ệ
U
 V
À
G
IẢ
I T
H
U
Ậ
T
16
1 2 4 6 9 10
X=-1
L
L=0
R=-1 => không tìm thấy X=-1
7
1 2 3 4 5 60
RM
Minh Họa Thuật Toán Tìm Nhị Phân (tt)
C
Ấ
U
 T
R
Ú
C
 D
Ữ
LI
Ệ
U
 V
À
G
IẢ
I T
H
U
Ậ
T
17
Các Bước Thuật Toán Tìm Kiếm Nhị Phân
¾ Giả sử dãy tìm kiếm hiện hành bao gồm các phần tử
nằm trong aleft, aright, các bước của giải thuật như sau:
¾ Bước 1: left=0; right=N-1;
¾ Bước 2: 
ƒ mid=(left+right)/2; //chỉ số phần tử giữa dãy hiện hành
ƒ So sánh a[mid] với x. Có 3 khả năng
• a[mid]= x: tìm thấy. Dừng
• a[mid]>x : Right= mid-1; 
• a[mid]<x : Left= mid+1;
¾ Bước 3: Nếu Left <=Right ; // còn phần tử trong dãy hiện
hành
+ Lặp lại bước 2
Ngược lại : Dừng
C
Ấ
U
 T
R
Ú
C
 D
Ữ
LI
Ệ
U
 V
À
G
IẢ
I T
H
U
Ậ
T
18
Cài Đặt Thuật Toán Tìm Nhị Phân
¾ Hàm trả về giá trị 1 nếu tìm thấy, ngược lại hàm
trả về giá trị 0
int BinarySearch(int a[],int n,int x)
{ int left, right, mid; left=0; right=n-1;
do{ 
mid=(left+right)/2;
if(a[mid]==x) return mid;
else if(a[mid]<x) left=mid+1;
else right=mid-1;
}while(left<=right);
return -1;
}
hung
7
C
Ấ
U
 T
R
Ú
C
 D
Ữ
LI
Ệ
U
 V
À
G
IẢ
I T
H
U
Ậ
T
19
Ðánh Giá Thuật Toán Tìm nhị phân
Trường hợp Css
Xấu nhất
Trung bình
log2N 
log2N / 2
¾ Độ phức tạp O(log2N)
Tốt nhất 1 
C
Ấ
U
 T
R
Ú
C
 D
Ữ
LI
Ệ
U
 V
À
G
IẢ
I T
H
U
Ậ
T
20
NHẬN XÉT - KẾT LUẬN
20
C
Ấ
U
 T
R
Ú
C
 D
Ữ
LI
Ệ
U
 V
À
G
IẢ
I T
H
U
Ậ
T
21
CHƯƠNG TRÌNH MINH HỌA
#define MAX 1000
void TaoMang(int a[], int N);
void XuatMang(int a[], int N);
int LinearSearch(int a[], int N);
void main()
{
int a[MAX], N = 20, x, kq;
TaoMang(a, N); XuatMang(a, N);
printf(“Nhap gia tri can tim: “); scanf(“%d”,&x);
kq=LinearSearch(a, N, x);
if(kq==-1) printf(“\n Khong co phan tu can tim”);
else printf(“\n Phan tu can tim xuat hien tai vi tri: %d” , kq);
}
21
hung
8
C
Ấ
U
 T
R
Ú
C
 D
Ữ
LI
Ệ
U
 V
À
G
IẢ
I T
H
U
Ậ
T
22
void TaoMang(int a[], int N)
{
for(int i=0; i<N; i++)
a[i]=rand()%N;
}
void XuatMang(int a[], int N)
{
for(int i=0; i<N; i++)
printf(“%d ”, a[i]);
}
22
C
Ấ
U
 T
R
Ú
C
 D
Ữ
LI
Ệ
U
 V
À
G
IẢ
I T
H
U
Ậ
T
23
int LinearSearch(int a[], int N, int x)
{
int i=0;
while ((i<N) && (a[i]!=x )) 
i++;
if(i==N)
return -1; // tìm hết mảng nhưng không có x
else
return i; // a[i] là phần tử có khoá x
}
C
Ấ
U
 T
R
Ú
C
 D
Ữ
LI
Ệ
U
 V
À
G
IẢ
I T
H
U
Ậ
T
24
BÀI TẬP LÝ THUYẾT
¾LT1_1: Cho dãy số sau:
Cho biết vị trí tìm thấy và số lần so sánh để
tìm được phần tử có giá trị x = 6 khi áp dụng 
giải thuật tìm kiếm: tuyến tính và nhị phân.
¾LT1_2: Xây dựng giải thuật tìm kiếm phần tử
có giá trị nhỏ nhất trong dãy số: Dùng mã giả
3 4 6 6 12 16 21 34 41 80
0 1 2 3 4 5 6 7 8 9
hung
9
C
Ấ
U
 T
R
Ú
C
 D
Ữ
LI
Ệ
U
 V
À
G
IẢ
I T
H
U
Ậ
T
25
BÀI TẬP THỰC HÀNH
1.Cài đặt các thuật toán tìm kiếm
2. Xây dựng và cài đặt thuật toán tìm:
a) Phần tử lớn nhất (hay nhỏ nhất).
b) Tất cả các số nguyên tố.
c) Dây dựng mảng cấu trúc sinh viên gồm 
masv, hoten, dtb viết chương trình có chức 
năng nhập – xuất – tìm kiếm sinh viên
25
C
Ấ
U
 T
R
Ú
C
 D
Ữ
LI
Ệ
U
 V
À
G
IẢ
I T
H
U
Ậ
T
26
BÀI TẬP THỰC HÀNH
¾CT1_1: Viết chương trình minh họa 2 giải 
thuật tìm kiếm trên để xác định tự động số
lần so sánh và vị trí tìm thấy (giả sử dãy 
số đầu vào có thứ tự tăng dần)
¾CT1_2: Cải tiến chương trình CT1_1 sao 
cho: Nếu dãy không có thứ tự thì tìm theo 
phương pháp tuyến tính. Ngược lại dãy 
có thứ tự thì tìm theo phương pháp nhị
phân 26
C
Ấ
U
 T
R
Ú
C
 D
Ữ
LI
Ệ
U
 V
À
G
IẢ
I T
H
U
Ậ
T
27
HƯỚNG DẪN CT1_1
Viết các hàm
¾Tạo ngẫu nhiên mảng một chiều số nguyên có thứ
tự tăng dần gồm N phần tử cho trước
void PhatSinhMangTang(int a[], int N)
¾Xem mảng phát sinh
void XuatMang(int a[], int N)
¾Tìm tuyến tính có chèn vào giá trị tính số lần so sánh
int TimTuyenTinh(int a[], int N, int X, int &ss=0)
¾Tìm nhị phân có chèn vào giá trị tính số lần so sánh
int TimNhiPhan(int a[], int N, int X, int &ss=0)
27
hung
10
C
Ấ
U
 T
R
Ú
C
 D
Ữ
LI
Ệ
U
 V
À
G
IẢ
I T
H
U
Ậ
T
28
HƯỚNG DẪN CT1_2
Viết các hàm
¾Tạo ngẫu nhiên mảng một chiều số nguyên 
gồm N phần tử
¾Xem mảng phát sinh
¾Kiểm tra xem mảng có thứ tự không (nếu 
có: Phải xác định là tăng hay giảm)
¾Tìm tuyến tính có chèn vào giá trị tính số lần 
so sánh
¾Tìm nhị phân có chèn vào giá trị tính số lần 
so sánh
28