Giảng viên : Nguyễn Minh Thành
Email : thanhnm@itc.edu.vn
Chương 2 (1) : Giải Thuật Tìm Kiếm
Nội Dung
I. Giới thiệu
II. Giải thuật tìm kiếm
III. Tìm kiếm tuyến tính
IV. Tìm kiếm nhị phân
2Nguyễn Minh Thành
I. Giới Thiệu
3Nguyễn Minh Thành
Tìm kiếm : là duyệt một danh sách và lấy ra phần tử thoả tiêu
chuẩn cho trước
Là một thao tác phổ biến trên máy tính và trong các ứng dụng
Tìm kiếm 1 dòng trong CSDL
Tìm kiếm hồ sơ, tập tin
Tìm kiếm 1 người trong một danh sách
…
Việc tìm kiếm nhanh thông tin trong một lượng lớn thông tin là
một điều cần thiết.
Các giải thuật tìm kiếm
II. Giải thuật tìm kiếm
4Nguyễn Minh Thành
Khảo sát việc tìm kiếm thường trên mảng và danh sách.
Có nhiều loại :
Tìm kiếm tuyến tính (tuần tự)
Tìm kiếm nhị phân
…
Cấu trúc :
Input
Mảng A gồm n phần tử
Giá trị x cần tìm
Output
Vị trí x trong A hoặc -1 nếu không tồn tại x
Thao tác cơ bản
So sánh
III. Tìm Kiếm Tuyến Tính
5Nguyễn Minh Thành
Có 2 loại tìm kiếm tuyến tính :
Vét cạn (exhaustive)
Dùng lính canh (sentinel)