Chương 2 (1) : Giải Thuật Tìm Kiếm
Giảng viên : Nguyễn Minh Thành Email : thanhnm@itc.edu.vn
Nội Dung I. Giới thiệu II. Giải thuật tìm kiếm III. Tìm kiếm tuyến tính IV. Tìm kiếm nhị phân
Nguyễn Minh Thành
2
I. Giới Thiệu Tìm kiếm : là duyệt một danh sách và lấy ra phần tử thoả tiêu
chuẩn cho trước
Là một thao tác phổ biến trên máy tính và trong các ứng dụng
Tìm kiếm 1 dòng trong CSDL Tìm kiếm hồ sơ, tập tin Tìm kiếm 1 người trong một danh sách …
Việc tìm kiếm nhanh thông tin trong một lượng lớn thông tin là
một điều cần thiết. Các giải thuật tìm kiếm
Nguyễn Minh Thành
3
II. Giải thuật tìm kiếm Khảo sát việc tìm kiếm thường trên mảng và danh sách. Có nhiều loại :
Tìm kiếm tuyến tính (tuần tự) Tìm kiếm nhị phân …
Cấu trúc : Input
Mảng A gồm n phần tử Giá trị x cần tìm
Output
Vị trí x trong A hoặc -1 nếu không tồn tại x
4
Thao tác cơ bản
So sánh Nguyễn Minh Thành
III. Tìm Kiếm Tuyến Tính Có 2 loại tìm kiếm tuyến tính :
Nguyễn Minh Thành
5
Vét cạn (exhaustive) Dùng lính canh (sentinel)
III. Tìm Kiếm Tuyến Tính – Vét Cạn Thuật toán :
Lần lượt so sánh x với các phần tử của mảng A cho đến khi
gặp được phần tử cần tìm, hoặc hết mảng.
Nguyễn Minh Thành
6
Ví dụ: A = {1, 25, 6, 5, 2, 37, 40}, x = 6
III. Tìm Kiếm Tuyến Tính – Vét Cạn Cài đặt 1 :
int LinearExhaustive(int a[], int N, int x) {
int i=0;
while ((i 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 Nguyễn Minh Thành 7 } Nguyễn Minh Thành 8 Mỗi vòng lặp có 2 điều kiện cần kiểm tra: Kiểm tra cuối mảng
Kiểm tra phần tử hiện tại có bằng x hay không? Trường hợp xấu nhất nằm ở cuối mảng A Ta có 2*n+1 số phép so sánh Nguyễn Minh Thành 9 => Số phép so sánh tăng/giảm tuyến tính theo số phần tử
Vậy độ phức tạp của thuật toán là : O(n) Có thể bỏ việc kiểm tra điều kiện cuối mảng bằng cách dùng Lính canh là phần tử có giá trị bằng với phần tử cần tìm và đặt Nguyễn Minh Thành 10 Tìm tuần tự từ đầu mảng cho đến khi tìm thấy x (chắc chắn sẽ Nếu x được tìm thấy tại vị trí lính canh thì x không thuộc mảng Nguyễn Minh Thành 11 Ngược lại trả về vị trí của x trong mảng A. int LinearSentinel(int a[],int N,int x)
{ int i=0; // mảng gồm N phần tử từ a[0]..a[N-1]
a[N] = x; // thêm phần tử thứ N+1 while (a[i]!=x )
i++; if (i==N) return -1; // tìm hết mảng nhưng không có x else return i; // tìm thấy x tại vị trí i Nguyễn Minh Thành 12 } int LinearSentinel(int a[], int n, int x)
{ a[n] = x; //đặtlínhcanh for (int i=0; ;i++) if (a[i] == x) break; if(i==n) i=-1; return i; Nguyễn Minh Thành 13 } Nguyễn Minh Thành 14 Với n=15000: nhanh hơn khoảng 20% (0.22s so với 0.28s) Thuật toán tìm kiếm nhị phân Input: Dãy A, n phần tử đã được sắp xếp
Giá trị x cần tìm Nguyễn Minh Thành 15 Output: giống với thuật toán tìm kiếm tuần tự So sánh x với phần tử chính giữa mảng A.
Nếu x là phần tử giữa thì dừng. Nguyễn Minh Thành 16 Lặp lại 2 bước trên với nửa đã được xác định. 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 Nguyễn Minh Thành 17 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 Nguyễn Minh Thành 18 // tìm kiếm trên tất cả các phần tử // lấy mốc so sánh mid = (left+right)/2;
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: //tìm tiếp x trong dãy con aleft .. amid -1 a[mid] < x: right =mid - 1; //tìm tiếp x trong dãy con amid +1 .. aright left = mid + 1; Bước 3: //còn phần tử chưa xét tìm tiếp. Nếu left <= right
Lặp lại Bước 2. Nguyễn Minh Thành 19 Ngược lại: Dừng //Ðã xét hết tất cả các phần tử. int BinarySearch(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 Nguyễn Minh Thành 20 } Nguyễn Minh Thành 21 Vậy độ phức tạp của thuật toán : O(log2n)
Một số so sánh : Nguyễn Minh Thành 22 Tuy nhiên, mảng phải được sắp xếp trước. Nguyễn Minh Thành 23III. Tìm Kiếm Tuyến Tính – Vét Cạn
Cài đặt 2 :
int LinearExhaustive(intA[], intn, intx)
{
for(int i=0; i
if(A[i]==x)
return i;
return -1;
}
III. Tìm Kiếm Tuyến Tính – Vét Cạn
Phép so sánh là phép toán sơ cấp được dùng trong thuật toán->
số lượng các phép so sánh sẽ là thước đo độ phức tạp của thuật
toán.
III. Tìm Kiếm Tuyến Tính – Lính Căn
Trong thuật toán vét cạn, có 2 điều kiện được kiểm tra:
“lính canh”.
ở cuối mảng.
Thuật toán lính căn
III. Tìm Kiếm Tuyến Tính – Lính Căn
Thuật toán lính căn
tìm thấy x)
A.
III. Tìm Kiếm Tuyến Tính – Lính Căn
Cài đặt 1 :
III. Tìm Kiếm Tuyến Tính – Lính Căn
Cài đặt 2 :
III. Tìm Kiếm Tuyến Tính – Lính Căn
Số phép so sánh trong trường hợp xấu nhất : n+2
Vậy độ phức tạp của thuật toán là O(n)
Tuy nhiên, thực nghiệm cho thấy trong trường hợp n lớn, thời gian
tìm kiếm giảm khi dùng phương pháp lính canh.
IV. Tìm Kiếm Nhị Phân
Khi một mảng đã được sắp thứ tự, tận dụng điều này ta có thể giảm
một số thao tác cho thuật toán tìm kiếm.
IV. Tìm Kiếm Nhị Phân
Ý tưởng
Nếu không : xác định xem x có thể thuộc nửa trái hay nửa phải
của A.
IV. Tìm Kiếm Nhị Phân
Ví dụ : tìm x = 41
x
x
x
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
IV. Tìm Kiếm Nhị Phân
Ví dụ : tìm x = 45
x
x
x
x
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
l > r: Kết thúc:
Không tìm thấy
m
m
IV. Tìm Kiếm Nhị Phân
Các bước của giải thuật
Bước 1: left = 1; right = N;
Bước 2:
IV. Tìm Kiếm Nhị Phân
Cài đặt 1
IV. Tìm Kiếm Nhị Phân
Cài đặt 2 (đệ quy)
int BinarySearch(int a[], int l, int r, int x)
{
if(r < l) return -1;
m = (l + r) / 2;
if ( x < a[m])
BS(a,l,m-1,x);
else if (x > a[m])
BS(a,m+1,r,x);
return m; //là phần tửchính giữa
}
IV. Tìm Kiếm Nhị Phân
Trường hợp xấu nhất là x nằm ở cuối mảng, số phép so sánh phải
thực hiện là : log2n + 1
Hỏi Đáp
