Chương 2 (1) : Giải Thuật Tìm Kiếm
Giảng viên : Nguyễn Minh Thành
Email :


Nội Dung
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
I.

2

Nguyễn Minh Thành


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


3

 Vét cạn (exhaustive)
 Dùng lính canh (sentinel)

Nguyễn Minh Thành


III. Tìm Kiếm Tuyến Tính – Vét Cạn


6

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.
 Ví dụ: A = {1, 25, 6, 5, 2, 37, 40}, x = 6

Nguyễn Minh Thành


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





9

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.
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
=> 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)

Nguyễn Minh Thành


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:
 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ính canh là phần tử có giá trị bằng với phần tử cần tìm và đặt
ở cuối mảng.
 Thuật toán lính căn



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
}

12

Nguyễn Minh Thành


III. Tìm Kiếm Tuyến Tính – Lính Căn


Cài đặt 2 :
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;
}

13

Nguyễn Minh Thành


III. Tìm Kiếm Tuyến Tính – Lính Căn

16

Ý tưởng
 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.
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.
 Lặp lại 2 bước trên với nửa đã được xác định.

Nguyễn Minh Thành


IV. Tìm Kiếm Nhị Phân


Ví dụ : tìm x = 41
x

x

3

14

16

19

22


l

Tìm thấy x tại
vị trí 6
m
r

m

m

17

x

Nguyễn Minh Thành


IV. Tìm Kiếm Nhị Phân


Ví dụ : tìm x = 45
x

x

x

x


6

7

8

9

10

l

m

m

r
l > r: Kết thúc:
Không tìm thấy

m

m

18

Nguyễn Minh Thành


IV. Tìm Kiếm Nhị Phân

Cài đặt 1
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