TS. Lê Minh Trung
ThS Lương Trần Ngọc Khiết
Khoa CNTT, Đại học Sư phạm, TP. HCM
Nội dung
Giới thiệu bài toán tìm kiếm
Tìm kiếm tuần tự
Tìm kiếm nhị phân
Khái niệm tìm kiếm
Cho biết:
Một danh sách các bản ghi (record).
Một khóa cần tìm.
Tìm bản ghi có khóa trùng với khóa cần tìm (nếu có).
Đo độ hiệu quả:
Số lần so sánh khóa cần tìm và khóa của các bản ghi
Phân loại:
Tìm kiếm nội (internal searching)
Tìm kiếm ngoại (external searching)
Tìm kiếm tuần tự
Input: mảng đầu vào int a[n], khóa cần tìm key
Output: vị trí tìm thấy đầu tiên của key trong mảng
hoặc -1 nếu không tìm thấy
int SequentialSearch(int a[n], int key)
{
for(int i=0; i<n; i++)if(a[i]==key)break;
if(i<n)return i;
return -1;
}
Tìm tuần tự (sequential search)
5
Target key
713 521 6 2 8 15
0 1 2 3 4 5 6 7
position = 2
return success
Số lần so sánh: 3