CHƯƠNG 4
CÁC THUẬT TOÁN TÌM
KIẾM
2/37
I. KHÁI NIỆM TÌM KIẾM
1. Đặt vấn đề CHÌA KHÓA
CỦA TA ĐÂU?
3/37
I. KHÁI NIỆM TÌM KIẾM
2. 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
(đối tượng cần tìm) trong một tập các đối
tượng cho trước (không gian tìm kiếm)
Ví dụ: Tìm một chùm chìa khóa trong một
gian phòng
Ta có hình ảnh của chùm chìa khóa
Gian phòng gồm nhiều đồ đạc
4/37
3. BÀI TOÁN TÌM KIẾM
- Dãy a, có n đối tượng, mỗi đối tượng có một
“khóa tìm kiếm”
- Khóa của đối tượng cần tìm (Key)
- Nếu tìm thấy đối tượng có khóa ‘Key’ trong
dãy a trả lại giá trị 1, ngược lại trả lại giá trị 0.
Dữ liệu vào:
Dữ liệu ra:
Ví dụ:
51682
Dữ liệu vào: a0 a1 a2 a3 a4
Số x=6
Dữ liệu ra: 1 (Tìm thấy x trong mảng a)
5/37
II. 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