1
Spring 2004Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM1
pTrình bày các thuật toán
thông dụng cho việc tìm
kiếm (Tìm tuần tự, tìm nhị
phân)
p Minh họa các thuật toán
p Đánh giá thuật toán
Tìm kiếm -Searching
Spring 2004Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM2
Công dụng
p Tìm kiếm trong một danh sách các phần tử
là một thao tác thường sử dụng trên máy
tính
p Ví dụ:
p Cơ sở dữ liệu (Database): tìm 1 sinh viên, tìm 1
tài khoản ngân hàng,…
p Internet: Yahoo!, Google,…
2
Spring 2004Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM3
Các phương pháp phổ biến
p Tìm tuần tự (Serial Search)
p Đơn giản
p Chi phí O(n)
p Tìm nhị phân
p Phải là 1 danh sách “đặc”
p Dữ liệu cần được sắp thứ tự
p Chi phí trung bình O(log
2
n)
Spring 2004Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM4

+
=
++++ n
n
nn
n
n
4
Spring 2004Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM7
Tìm nhị phân
(Binary Search)
p Các phần tử được sắp
p n= 8
p key = 16
p Xét phần tử giữa
m= n/2
p Nếu (a[m]==key)
à Kết thúc !
p Nếu(key< a[m])
Xét ½ dãy bên trái
p Nếu (key > a[m])
Xét ½ dãy bên phải
181612107632
[0] [1] [2] [3] [4] [5] [6] [7]
Spring 2004Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM8
Tìm nhị phân
(Binary Search)
181612107632
[0] [1] [2] [3] [4] [5] [6] [7]
[5][6][7]