Chương 2.1. Giải thuật tìm kiếm
Võ Quang Hoàng Khang Email: vqhkhang@gmail.com
1
Mục tiêu
Xác định được vai trò của tìm kiếm và sắp xếp
trong hệ thống thông tin
Nắm vững và minh họa được giải thuật tìm
kiếm tuyến tính và tìm kiếm nhị phân trên
mảng một chiều
Cài đặt được giải thuật tìm kiếm bằng ngôn
ngữ C/C++
2
Suy nghĩ
?
Tại sao hầu hết phần mềm phải có chức năng tìm kiếm và sắp xếp, mối quan hệ giữa tìm kiếm và sắp xếp?
3
Nhu cầu tìm kiếm và sắp xếp
Thao tác tìm kiếm được sử dụng nhiều nhất trong các hệ lưu trữ và quản lý dữ liệu.
Do dữ liệu lớn nên tìm ra giải thuật tìm kiếm nhanh chóng là mối quan tâm hàng đầu. Để đạt được điều này dữ liệu phải được tổ chức theo một thứ tự nào đó thì việc tìm kiếm sẽ nhanh chóng và hiệu quả hơn, vì vậy nhu cầu sắp xếp dữ liệu cũng được lưu ý.
Tóm lại, bên cạnh những giải thuật tìm kiếm thì các giải thuật sắp xếp dữ liệu không thể thiếu trong hệ quản lý thông tin trên máy tính.
4
Các giải thuật tìm kiếm
…
Có 2 giải thuật thường được áp dụng: Tìm tuyến tính và tìm nhị phân. Đặc tả như sau: a4
an-1 aN
a2
a3
a5
a1
Tập dữ liệu được lưu trữ là dãy số a1, a2, ... ,aN. Giả sử chọn cấu trúc dữ liệu mảng để lưu trữ dãy số này trong bộ nhớ chính, có khai báo: int a[N]; Khoá cần tìm là x, được khai báo như sau: int x;
5
Tìm kiếm tuyến tính Ý tưởng Lần lượt so sánh x với phần tử thứ nhất, thứ hai, ... của mảng a cho đến khi gặp được phần tử cần tìm, hoặc đã tìm hết mảng mà không thấy x Minh họa tìm x =10
10
7
5
12
41
10 10
32
13
15
3
9
Đã tìm Chưa thấy tại hết vị trí 5 mảng
1
2
3
4
5
6
7
9
10
8
Minh họa tìm x =25
25
Chưa hết Đã hết mảng mảng
7
5
12
41
10
32
13
15
3
9
1
2
3
4
5
6
7
9
10
8
6
// bắt đầu từ phần tử đầu tiên của dãy
Giải thuật Bước 1: i = 1; Bước 2: So sánh a[i] với x, có 2 khả năng : a[i] = x : Tìm thấy. Dừng a[i] != x : Sang Bước 3. Bước 3: i = i+1; // xét tiếp phần tử kế trong mảng Nếu i >N: Hết mảng, không tìm thấy. Dừng
Ngược lại: Lặp lại Bước 2.
7
Nguyên tắc cài đặt hàm tìm kiếm
Nếu có xuất hiện phần tử có giá trị x thì trả về
vị trí tìm được
Ngược lại thì trả về -1
8
Cài đặt int TimTuyenTinh(int a[], int N, int x) {
int i=0;
while ((i i++; }
if(i==N) return -1; //tìm hết mảng else return i; //a[i] là phần tử có khoá x } Dùng lính canh giúp giảm bớt phép so sánh
Minh họa tìm x =10 11 3 4 5 6 7 9 10 1 2 8 Minh họa tìm x = 25 1 2 8 3 4 5 6 7 9 10 25
25
11 int i=0;
a[N] = x; // thêm phần tử x sau mảng
while (a[i]!=x )
i++; if (i==N) return -1; // tìm hết mảng else return i; // tìm thấy x tại vị trí i }
Độ phức tạp tính toán cấp n: T(n)=O(n) Áp dụng đối với những dãy số đã có thứ tự. Tại mỗi bước tiến hành so sánh x với phần tử nằm ở vị trí giữa của dãy tìm kiếm hiện hành, dựa vào kết quả so sánh này để quyết định phạm vi tìm kiếm ở bước kế tiếp. x x x 2
2
2
2 3
3
3
3 4
4
4
4 1
1
1
1 8
8
8
8 7
7
7
7 9
9
9
9 10
10
10
10 5
5
5
5 6
6
6
6 14
14
14
14 16
16
16
16 19
19
19
19 3
3
3
3 51
51
51
51 46
46
46
46 63
63
63
63 71
71
71
71 22
22
22
22 41
41
41
41 Tìm thấy x tại
vị trí 6 l m r m m x x x x 2
2
2
2
2 3
3
3
3
3 4
4
4
4
4 1
1
1
1
1 8
8
8
8
8 9
9
9
9
9 10
10
10
10
10 5
5
5
5
5 6
6
6
6
6 7
7
7
7
7 14
14
14
14
14 16
16
16
16
16 19
19
19
19
19 3
3
3
3
3 51
51
51
51
51 63
63
63
63
63 71
71
71
71
71 22
22
22
22
22 41
41
41
41
41 46
46
46
46
46 l m r m m m //tìm tiếp x trong dãy con aleft .. amid -1 right =mid - 1; a[mid] < x: //tìm tiếp x trong dãy con amid +1 .. aright left = mid + 1; Bước 3: Nếu left <= right //còn phần tử chưa xét tìm tiếp. Lặp lại Bước 2. Ngược lại: Dừng //Ðã xét hết tất cả các phần tử. int TimNhiPhan( int a[], int N, int x )
{ int left =0; right = N-1;
int mid;
do
{ mid = (left + right)/2;
if (x == a[mid]) return mid;//Thấy x tại mid else if (x < a[mid]) right = mid -1; else left = mid +1; } while (left <= right); return -1; // Tìm hết dãy mà không có x }
Độ phức tạp tính toán cấp n: T(n)=O(log 2n) #include void main()
{ srand((usigned int) time (NULL));
int a[MAX], N = 20, x, kq;
TaoMang(a, N);
XuatMang(a, N);
cout<<“Nhap gia tri can tim: “;
cin>>x;
kq=LinearSearch(a, N, x);
if(kq==-1) cout<<“Khong co phan tu can tim”; else cout<<“Phan tu can tim tai vi tri: ”< } void TaoMang(int a[], int N)
{ for(int i=0; i }
void XuatMang(int a[], int N)
{ for(int i=0; i } int LinearSearch(int a[], int N, int x)
{ int i=0;
while ((i i++; if(i==N) return -1; else return i; } 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ã tự
nhiên, mã giả và lưu đồ. Viết chương trình tự động phát sinh ra mảng có giá trị ngẫu nhiên có thứ tự tăng dần; nhập vào giá trị cần tìm x; in ra vị trí xuất hiện của x (nếu có) và số lần so sánh với mỗi phương pháp tìm kiếm: tuyến tính và nhị phân9
Cải tiến
10
10
12
41
10
10
32
13
15
3
7
5
9
25
7
5
9
12
41
10
32
13
15
3
10
Cài đặt
int TimTuyenTinh2(int a[],int N,int x)//cải tiến
{
11
Tìm kiếm nhị phân
Ý tưởng
12
Minh họa tìm x = 41
13
Minh họa tìm x = 45
l > r: Kết thúc:
Không tìm thấy
14
Giải thuật
Bước 1: left = 1; right = N; //tìm kiếm tất cả các phần tử
Bước 2:
mid = (left+right)/2; // lấy mốc so sá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:
15
16
Code minh họa
17
18
19
20
Bài tập lý thuyết
3
0
4
1
6
2
6
3
12
4
16
5
21
6
34
7
41
8
80
9
21
Bài tập viết chương trình
22
