Cấu trúc dữ liệu và giải thuật
Bài 8: Các thuật toán tìm kiếm
PhD. Ngo Huu Phuc, Le Quy Don Technical University
1
Giảng viên: TS. Ngo Huu Phuc
Tel: 0438 326 077
Mob: 098 5696 580
Email: ngohuuphuc76@gmail.com
Bài 8. Các thuật toán tìm kiếm
Nội dung:
8.1. Khái niệm về tìm kiếm (3)
8.2. Phương pháp tìm kiếm tuần tự (7)
8.3. Phương pháp tìm kiếm nhị phân (8)
8.4. Phương pháp tìm kiếm nội suy (7)
Tham khảo:
1. Data structures and Algorithms Searching.htm
2. Kyle Loudon Mastering Algorithms, Chapter 12 Sorting and Searching
3. Lecture 19 Sequential and Binary Search.htm
4. Sedgewick Algorithms, Elementary Searching Methods
5. Bài giảng của TS Nguyễn Nam Hồng
PhD. Ngo Huu Phuc, Le Quy Don Technical University
2
8.1. Khái niệm về tìm kiếm (1/3)
Trong thực tế, việc xác định vị trí của một phần tử nào đó
trong một danh sách ( đã sắp xếp hoặc chưa sắp xếp) có
ý nghĩa quan trọng và được dùng trong nhiều ứng dụng.
Ví dụ 1: một chương trình tra cứu từ điển, chương trình
cần trả lời ngay nghĩa của một từ nào đó.
Ví dụ 2: trong một danh sách thí sinh, chương trình cần
đưa ra tất cả thông tin của thí sinh thỏa mãn một số tiêu
chí nào đó.
Những bài toán như vậy được gọi chung là bài toán tìm
kiếm.
PhD. Ngo Huu Phuc, Le Quy Don Technical University
3
8.1. Khái niệm về tìm kiếm (2/3)
Trong thực tế, với các ý tưởng khác nhau dẫn
đến các phương pháp tìm kiếm khác nhau.
Phương pháp tìm kiếm thông dụng nhất trong
thực tế là tìm kiếm tuần tự. Đây là phương pháp
đơn giản, tuy nhiên mất nhiều thời gian thực hiện
đối với dữ liệu lớn.
PhD. Ngo Huu Phuc, Le Quy Don Technical University
4
8.1. Khái niệm về tìm kiếm (3/3)
Phương pháp tìm kiếm nhị phân: chia danh sách thành
các danh sách con và tìm kiếm trên đó. Với bộ dữ liệu lớn,
phương pháp này cho tốc độ tìm kiếm tốt hơn phương
pháp tuần tự.
Phương pháp tìm kiếm nội suy: cũng giống như
phương pháp tìm kiếm nhị phân, phương pháp này cũng
chia danh sách thành các danh sách con và tìm kiếm trên
đó.
Phương pháp tìm kiếm nội suy nhanh hơn phương pháp
nhị phân vì chúng dự đoán kết quả tìm kiếm trên phần nào
để thực hiện tìm kiếm.
PhD. Ngo Huu Phuc, Le Quy Don Technical University
5