CÁC GI I THU T Ả Ậ
TÌM KI MẾ
1
2. CÁC GI I THU T TÌM KI MẢ Ậ Ế
Có 2 gi i thu t th ng đ c áp d ng: ả ậ ườ ượ ụ Tìm tuy n tính ếvà
tìm nh phânị.
Đ đ n gi n cho vi c minh h a, ta đ c t nh sau:ể ơ ả ệ ọ ặ ả ư
T p d li u đ c l u tr là dãy sậ ữ ệ ượ ư ữ ố a , a , ... ,a .
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];
Khoá c n tìm là ầx, đ c khai báo nh sau: ượ ư int x;
2
a1a2a3a4a5… an-1 aN
Ch a ư
h t ế
m ngả
3. Tìm ki m tuy n tínhế ế
Ý t ng ưở
Ti n hành so sánh ếx l n l t v i ph n t th nh t, th ầ ượ ớ ầ ử ứ ấ ứ
hai, ... c a m ng ủ ả a cho đ n khi g p đ c ph n t cóế ặ ượ ầ ử
khóa c n tìm, ho c đã tìm h t m ng mà không th y ầ ặ ế ả ấ x.
Minh h a tìm x =10ọ
Minh h a tìm x =25ọ
3
7 5 12 41 10 32 13 9 15 3
12345678910
7 5 12 41 10 32 13 9 15 3
12345678910
10
10
25
Ch a ư
h t ế
m ngả
Đã tìm
th y t i ấ ạ
v trí 5ị
Đã h t ế
m ngả
Gi i thu t ả ậ
B c 1:ướ
i=1;//b tđ ut ph nt đ utiênc aắ ầ ừ ầ ử ầ ủ
dãy
B c 2:ướ
Sosánha[i]v ix,ớcó2kh năng:ả
a[i]=x:Tìmth y.D ngấ ừ
a[i]!=x:SangB c3.ướ
B c 3ướ :
i=i+1;//xétti pph nt k trongm ngế ầ ử ế ả
N ui>N:H tm ng,khôngtìmth y.D ngế ế ả ấ ừ
Ng cl i:L pl iB c2.ượ ạ ặ ạ ướ
4
Cài đ t ặ
intLinearSearch(inta[],intN,intx)
{
inti=0;
while((i<N)&&(a[i]!=x))
i++;
if(i==N)
return-1;//tìmh tm ngnh ngkhôngcóxế ả ư
else
returni;//a[i]làph nt cókhoáxầ ử
}
5