C u trúc d li u và gi i thu tấ ữ ệ ả ậ
N I DUNGỘ
CÁC THU T TOÁN TÌM KI MẬ Ế
C u trúc d li u và gi i thu tấ ữ ệ ả ậ
Bài toán tìm ki mế
•Input: Cho m ng a có n ph n tả ầ ử
•X: Giá tr c n tìmị ầ
•Output: Tìm ph n t có giá tr = x có hay không ầ ử ị
trong m ngả
=> Hai thu t toán tìm ki m:ậ ế
Tìm ki m tu n t (áp d ng trên m i m ng)ế ầ ự ụ ọ ả
Tìm ki m nh phân (áp d ng trên m ng đã có th t )ế ị ụ ả ứ ự
C u trúc d li u và gi i thu tấ ữ ệ ả ậ
Thu t toán tìm ki m tuy n tínhậ ế ế
•Ý t ngưở :L n l t so sánh X v i t ng ph n t ầ ượ ớ ừ ầ ử
trong A cho đ n khi tìm th y hay h t ph n t ế ấ ế ầ ử
trong m ng.ả
•Các b c ti n hànhướ ế
Bc 1ướ : Kh i gán i=1ở
B c 2ướ : So sánh a[i] v i giá tr x c n tìm, có 2 kh ớ ị ầ ả
năng
+ a[i]=x tìm th y x. D ng ấ ừ
+ a[i] # x sang b c 3ướ
B c 3ướ : i=i+1 //xét ti p ph n t k ti p trong m ngế ầ ử ế ế ả
N u i >N: H t m ng. D ngế ế ả ừ
Ng c l i: L p l i b c 2 ượ ạ ặ ạ ướ
C u trúc d li u và gi i thu tấ ữ ệ ả ậ
Thu t toán tìm ki m tuy n tínhậ ế ế
int LinearSearch(int a[],int n, int x)
{ int i=0;
while((i<n)&&(a[i]!=x))
i++;
if(i==n)
return 0; //Tìm không th y xấ
else
return 1;// tìm th yấ
}
C u trúc d li u và gi i thu tấ ữ ệ ả ậ
Thu t toán tìm ki m tuy n tínhậ ế ế
1 2 3 4 5 60
2 8 5 1 6 4 6
X=6
i
6
Tìm th y 6 t i v trí 4ấ ạ ị