KHOA CÔNG NGHỆ THÔNG TIN
CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT
GVGD:
1. THS. TRẦN CÔNG THANH
HỌC KỲ I – NĂM HỌC 2020-2021
KHÓA
BÀI 2: GIẢI THUẬT TÌM KIẾM
NỘI
DUNG
Tìm kiếm tuyến tính
02.
Tìm kiếm nhị phân
03.
04.
05.
Bài tập
06.
Giới thiệu bài toán tìm kiếm
01.
感谢您下载包图网平台上提供的PPT作品，为了您和包图网以及原创作者的利益，请勿复制、传播、销售，否则将承担法律责任！包图网将对作品进行维权，按照传播下载次数进行十倍的索取赔偿！
ibaotu.com
4
KHOA CÔNG NGHỆ THÔNG TIN
❖Tìm kiếm là quá trình xác định một đối tượng nào đó trong
một tập các đối tượng. Kết quả trả về:
• Đối tượng tìm được (nếu có)
• Chỉ số (nếu có) xác định vị trí của đối tượng trong tập đó.
❖Việc tìm kiếm dựa theo một trường nào đó của đối tượng,
trường này là khóa (key) của việc tìm kiếm.
Ví dụ: Tìm sinh viên có họ tên X trong DSSV.
SV {MaSV, HoTen, DiaChi,…}
Khoá?
Kết quả trả về?
1. Giới thiệu bài toán tìm kiếm
感谢您下载包图网平台上提供的PPT作品，为了您和包图网以及原创作者的利益，请勿复制、传播、销售，否则将承担法律责任！包图网将对作品进行维权，按照传播下载次数进行十倍的索取赔偿！
ibaotu.com
5
KHOA CÔNG NGHỆ THÔNG TIN
1. Giới thiệu bài toán tìm kiếm
Bài toán được mô tả như sau:
• Tập dữ liệu được lưu trữ là dãy a1, a2,..,an. Giả sử
chọn cấu trúc dữ liệu mảng để lưu trữ dãy số này
trong bộ nhớ chính, có khai báo: int a[n];
• Khóa cần tìm là x: int x;
Tìm kiếm
Tìm kiếm tuyến tính Tìm kiếm nhị phân
Tập dữ liệu
đã
được sắp
xếp
Tập dữ
liệu
bất kỳ