1
Bài 2: KThut Tìm Kim
(Searching)
GV: Nguyn Hu Th
Khoa CNTT –i Hc Cu Long
 
NI DUNG
1. Tìm kim tuyn tính
1
2. Tìm kim nhphân
2
5
 
1. Tìm kim tuyn tính (sequential search)
Gii thut
−
Thut toán tin hành so sánh x ln lt vi phn tthnht, th
hai, ... ca mng a cho n khi gp c phn tcó khóa cn tìm,
hoc ã tìm ht mng mà không thy x.
−
Các bc tin hành nh sau :
Bc 1:
i = 1; // bt u tphn tu tiên ca dãy
Bc 2: So sánh a[i] vi x, có 2 kh:
a[i] = x : Tìm thy. Dng
a[i] != x : c 3.
Bc 3 :
i = i+1; // xét tip phn tktrong mng
Nu i >N: Ht mng,không tìm thy.Dng
Ngc li: Lp li Bc 2.
 
1. Tìm kim tuyn tính (sequential search)
int LinearSearch(int a[], int n, int x)
{
int i=0;
while(i<n && a[i]!=x) i++;
if (i<n)
return i; ailà phn tcó khoá x
else
return -1; tìm ht mng nhng không có x
}
 
1. Tìm kim tuyn tính (sequential search)
int LinearSearch(int a[], int n, int x)
{
for(int i=0;i<n; i++)
{
if (a[i]==x)
return i; ailà phn tcó khoá x
}
return -1; tìm ht mng nhng không có x
}