1
CHƯƠNG 6
CÁC THU T TOÁN TÌM KI MẬ Ế

2/37
NỘI DUNG

Khái niệm tìm kiếm

Các phương pháp tìm kiếm

Phương pháp tìm kiếm tuần tự

Phương pháp tìm kiếm nhị phân

Phương pháp tìm kiếm trên cây nhị phân tìm kiếm

3/37
KHÁI NIỆM TÌM KIẾM
Đặt vấn đề
CHÌA KHÓA
CỦA TA ĐÂU?

4/37
KHÁI NIỆM TÌM KIẾM

Khái niệm

Tìm kiếm là việc kiểm tra xem có hay không
một đối tượng có một số thông tin cho trước

CÁC THUẬT TOÁN TÌM KIẾM

Tìm kiếm tuần tự

Tìm kiếm nhị phân

Tìm kiếm trên cây nhị phân tìm kiếm

7/37
CÁC THUẬT TOÁN TÌM KIẾM

Tùy theo dữ liệu vào ta có thể phân chia bài
toán tìm kiếm thành hại loại

Tìm kiếm trên dãy chưa sắp: dãy tìm kiếm
chưa được sắp xếp theo thứ tự khóa tìm
kiếm

Tìm kiếm trên dãy đã sắp: dãy tìm kiếm đã
sắp theo thứ tự tăng dần của khóa tìm kiếm

8/37
TÌM KIẾM TRÊN DÃY CHƯA SẮP

Với một dãy chưa được sắp xếp thì cách
tìm kiếm đơn giản nhất là tìm kiếm tuần tự

Tìm kiếm tuần tự là một phương pháp tìm
kiếm khá phổ biến và hết sức đơn giản
??


11/37
TÌM KIẾM TUẦN TỰ
Việc tìm kiếm có thể minh họa như sau

i=0; a0=5 <> x=6; i=i+1;

i=1; a1=1 <> x=6; i=i+1;

i=2; a2=6 = x; Tìm thấy x
Tìm kiếm kết thúc thành công
Chuyển sang đối tượng kế tiếp
Chuyển sang đối tượng kế tiếp

12/37

Ví dụ 2
TÌM KIẾM TUẦN TỰ
3 48 11 36 25 23 42 7
a0 a1 a2 a3 a4
- Cho dãy số
- Minh họa việc tìm số x1=42 và số x2=43 trong
dãy bằng phương pháp tìm kiếm tuần tự
a5 a6 a7

Ví dụ 2
a1
- Minh họa việc tìm số x1=42 và số x2=43 trong
dãy bằng phương pháp tìm kiếm tuần tự


Nhận xét : mỗi lần so sánh đều phải kiểm tra xem
dãy đã hết chưa (i<n), nên tốn thêm thời gian.

Để tránh điều đó người ta thêm đối tượng x vào
cuối dãy a (gán a[n]=x)
5 1 6 8 2
a0 a1 a2 a3 a4
5 1 6 8 2 6
a0 a1 a2 a3 a4 a5
Ví dụ

16/37
Giải thuật
TÌM KIẾM TUẦN TỰ CẢI TIẾN
i=0; a[n]=x
(x!= a[i])
i=i+1
Yes
(i<n)
No
No
return 0
Yes
return 1
end
begin

17/37
TÌM KIẾM TUẦN TỰ CẢI TIẾN
int tktt2(int x, int a[], int n)

cần tìm (tìm kiếm thành công)

Gặp đối tượng có khóa “lớn hơn” khóa của đối
tượng cần tìm (tìm kiếm không thành)

Đã duyệt hết dãy (tìm kiếm không thành)
TÌM KIẾM TUẦN TỰ TRÊN DÃY ĐÃ SẮP

20/37
TÌM KIẾM TUẦN TỰ TRÊN DÃY ĐÃ SẮP
Ví dụ:
1 2 5 6 8
a1 a1 a2 a3 a4
Tìm số x=4 trong dãy
Cho dãy số được
sắp tăng
i=0
x
4
i=1 i=2
1 2 5 6 8
Không tìm thấy x

21/37
Giải thuật
TÌM KIẾM TUẦN TỰ TRÊN DÃY ĐÃ SẮP
i=0; a[n]=x
( a[i]<x )
i=i+1
Yes

a[l], , a[m-1]

Nếu a[m] < x, tìm kiếm được thực hiện với dãy phải
a[m+1], , a[r]

Quá trình tìm kiếm tiếp tục cho đến khi gặp đối
tượng mong muốn (thành công) hoặc dãy khóa đang
xét trở nên rỗng
TÌM KIẾM NHỊ PHÂN

24/37

Ví dụ
TÌM KIẾM NHỊ PHÂN
1 2 5 6 8
a0 a1 a2 a4 a4
- Cho dãy số được sắp tăng
- Tìm số x=4 trong dãy
Quá trình tìm kiếm được minh họa như sau

25/37
TÌM KIẾM NHỊ PHÂN
Dãy đang xét
1 2 5 6 8
l=0, r=4, m=2
x
4
<
a[m]=5
1 2 5 6 8