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:

 a
1
, a
2
, ,a
N


         !     
" #$%&'()*#+",int a[N];

-"+./x')*#+"*,int x;
2
a
1
a
2
a
3
a
4

=
>?&6
<1


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

a[i]!=x:i=i+1;
Bước 3:

Nếui≤N:tìmthấyxtạivịtríi.

Ngượclại:khôngtìmthấyxtrongdãy.
7
Cài đặt
int LinearSearch2(int a[],int N,int x)
{ inti=0; //mảnggồmNphầntửtừa[0] a[N-1]
a[N]=x;//thêmphầntửthứN+1
while(a[i]!=x)
i++;
if(i==N)
return-1; //tìmhếtmảngnhưngkhôngcóx
else
returni; //tìmthấyxtạivịtríi
}

Ðánh giá giải thuật
Độ phức tạp tính toán cấp n: T(n)=O(n)
8
4. Tìm kiếm nhị phân
Ý tưởng

Áp dụng đối với những dãy số đã có thứ tự.

Giải thuật tìm cách giới hạn phạm vi tìm kiếm sau mỗi
lần so sánh x với một phần tử trong dãy. Ý tưởng của
giải thuật là tại mỗi bước tiến hành so sánh x với phần

3 14 16 19 22 41 46 51 63 71
2 3 4 5 6 7 8 9 : 2;
m
x
3 14 16 19 22 41 46 51 63 71
2 3 4 5 6 7 8 9 : 2;
r
m
x
l
3 14 16 19 22 41 46 51 63 71
2 3 4 5 6 7 8 9 : 2;
m
x
3 14 16 19 22 41 46 51 63 71
2 3 4 5 6 7 8 9 : 2;
l > r: Kết thúc:
Không tìm thấy
Giải thuật
D%2,EFG2H GIHJJ/)1K+.
D%3,
G@EFL BJ3HJJ"+
M"+*NO>%P'(4)Q ,

*NOGP,/RS 

*NOTP, JJ/1P" "*
EF
*
U2

Ðánh giá giải thuật
Độ phức tạp tính toán cấp n: T(n)=O(log
2
n)
13