KỸ THUẬT TÌM KIẾM (SEARCHING)

Môn: C U TRÚC D LI U

Ữ Ệ

Ấ

Ch

ươ

ng 2: K THU T TÌM KI M Ậ

Ỹ

Ế

(SEARCHING)

4 ti

t LTế

N I DUNG CH

NG 2

Ộ

ƯƠ

ế

i thu t tìm ki m n i (Tìm ki m trên m ng)

ế

ả

2.1 Khái quát v tìm ki m ề 2.2 Các gi ộ ế ậ ả  Tìm tuy n tính (Linear Search) ế  Tìm nh phân (Binary Search) ị 2.3 Các gi

i thu t tìm ki m ngo i (Tìm ki m trên t p ạ

ế

ậ

ả

tin)

ế ị

 Tìm tuy n tính (F Linear Search)  Tìm nh phân (Binary Search) BÀI T PẬ

2.1 Khái quát v tìm ki m

ề

ế

 Trong các h l u tr và qu n lý d li u, thao tác tìm ki m ả c th c hi n nhi u nh t đ khai thác thông tin m t các d ễ ấ ể

ữ ệ ữ ế

ệ ư ệ ự ề ộ

đ ượ dàng.  S l ệ ộ ố

 N u tìm ki m trong m t h th ng đã t

ng thông tin trong m t h th ng thông tin là đáng k ể i thu t tìm ki m nhanh s có ý nghĩa ế ẽ ậ ả ự

ộ ệ ố ổ ch c thì vi c tìm ki m ệ ứ ế

ả ượ c xây d ng nh m m c tiêu h tr ỗ ợ ự ụ ằ

ứ

ữ ệ ấ

ố ượ nên vi c xây d ng các gi ệ quan tr ng. ọ ế d dàng h n. ơ ậ ng d ng có hi u qu h n. ệ ậ ữ ệ ả ế i thu t tìm ki m đ ế ả ơ i thu t ph thu c vào vào c u trúc d li u mà nó tác ộ c l u tr trên b nh chính và b nh ớ ớ ượ ư ữ ộ ộ

ế ễ  Các gi ụ  Các gi ụ đ ng đ n. D li u đ ộ ph .ụ

2.1 Khái quát v tìm ki m (tt)

ề

ế

 Gi

đ ộ

s m i ph n t ả ử ỗ ậ ể ữ ệ ầ khóa i là ạ

c xem xét có m t thành ph n ầ ử ượ (Key) đ nh n di n có ki u d li u T, các thành ph n còn l ể ệ thông tin (Info), nh v y m i ph n t có c u trúc nh sau: ầ ử ư ậ ầ ư ấ ỗ

typedef struct DataElement {

T InfoData Key; Info;

} DataType;  Đ đ n gi n, quan tâm thành ph n d li u ch là khóa nh n ể ơ ữ ệ ả ầ ậ ỉ

di nệ

2.2 Các gi

ả

i thu t tìm ki m n i ộ

ế

ậ

Bài toán đ t ra: Gi s có m t m ng A g m n ph n t ặ ả ử ả ầ ồ

ị ằ

ầ ử X thì ph n t b ng ph n t X là ph n t . C n xác ộ ầ ử có giá tr b ng X trong m ng M?? ả th ầ ử ứ ầ ử ầ ử ằ

đ nh có hay không ph n t N u có ph n t ầ ử m y trong m ng X? ả ị ế ấ

ả ộ ư ế ậ

ế hay (Sequential Search) còn g i tìm ki m Các gi i thu t tìm ki m n i đ a ra 2 cách tìm ki m  Tìm ki m tu n t ế ầ ự ế ọ

 Tìm ki m nh phân (Binary Search)

ế

tuy n tính (Linear Search) ị ế

Tìm tuy n tính (Linear Seach)

ế

Ý t

ả

ầ ử ủ

ớ

ị đ u tiên cho đ n khi tìm

c a m ng A v i giá tr X ế

ầ ử ầ

ầ ượ ắ ầ ừ

ả

ấ

ph n t

ầ ử ầ

ng: ưở So sánh l n l t các ph n t ph n t c n tìm b t đ u t ầ th y ho c tìm h t m ng mà không tìm th y X. ế ặ ấ Thu t toán ậ đ u tiên B1: i = 1 ;// b t đ u t ắ ầ ừ B2: 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 B3 B3: i=i+1 // Xét ph n t

ả ừ

ấ

ti p theo trong m ng N u i>n : H t m ng, không tìm th y.D ng ế Ng

ế i: l p l

c l

ầ ử ế ả i B2 ượ ạ ặ ạ

ừ

Tìm tuy n tính (Linear Seach)

ế

Ví d :ụ

12 2 8 5 1

X=8 X=8

i=1

12 2 8 5 1

X=8 i=2

12 2 8 5 1

i=3

X=8

12 2 8 5 1

D ngừ 7

Tìm tuy n tính (Linear Seach)

ế

ậ

ặ

Cài đ t thu t toán: int LinearSearch (int A[], int n, int X) {

int i = 0; while (A[i] != X && i

m ng M tính t

ầ ử ả

ừ

i++; if (i < n)

return (i);

return (-1);

}

Tìm tuy n tính (Linear Seach)

ế

ậ

Phân tích, đánh giá thu t toán:  Tr

t nh t (ph n t

đ u tiên c a m ng có ủ

ả

ấ

ườ

ợ ố

ầ ử ầ

min = 1

min = 2+1=3

 Tr

nào c a

ầ ử

ủ

ấ ị

max = 1

ng h p t giá tr = X) ị  S phép gán G ố  S phép so sánh S ố ng h p x u nh t (không có ph n t ườ ấ ợ m ng có giá tr = X) ả  S phép gán G  S phép so sánh S

max = 2n + 1

avg = 1

 S phép gán G  S phép so sánh S

ố ố  Trung bình ố ố

avg = (3+2n + 1)/2=n+2

Tìm tuy n tính (Linear Seach)

ế

ự ệ ậ ớ

ả ớ

ị ằ

C i ti n thu t toán: ậ ả ế  M i b ỗ ướ ặ  ý t ưở m t ph n t ộ nh n di n ra s h t m ng khi duy t ệ . ự ế ậ c l p v i thu t toán trên c n th c hi n 2 phép so sánh ầ ng gi m b t phép so sánh b ng cách thêm vào m ng ằ ả c m canh (sentinel/stand by) có giá tr b ng X đ ầ ử ầ ể ệ ả

„ X

ặ ạ

có giá tr X i B3 ấ

i: Thì không tìm th y ph n t ầ ử ấ ầ ử v trí i ị ở ị có giá tr X ị

B1: i = 1 B2: A[i+1] = X B3: N u A[i] ế Thì i++ i: L p l Ng c l ượ ạ B4: N u i < N Thì Tìm th y ph n t ế B5: Ngu c l ợ ạ B6: K t thúc ế

Tìm tuy n tính (Linear Seach)

ế

ậ ặ ả ế

Cài đ t thu t toán c i ti n: int LinearSearchCaiTien (int A[], int n, int X) {

int i = 0; A[N] = X; // ph n t m ng A tính t 0 ầ ử ả ừ

while (A[i] != X)

i++;

if (i < i)

return (i);

return (-1);

}

Tìm tuy n tính (Linear Seach)

ế

ậ

ả ế

t nh t (ph n t

đ u tiên c a m ng có ủ

ả

ườ

ợ ố

ầ ử ầ

Phân tích, đánh giá thu t toán c i ti n:  Tr ấ

min = 2

 Tr

nào c a

ầ ử

ủ

ấ ị

max = 2

ng h p t giá tr = X) ị  S phép gán G ố  S phép so sánh S ố ng h p x u nh t (không có ph n t ườ ấ ợ m ng có giá tr = X) ả  S phép gán G  S phép so sánh S

max = (N + 1) + 1

avg = 2

 S phép gán G  S phép so sánh S

ố ố  Trung bình ố ố

avg = N/2 + 2

Tìm tuy n tính (Linear Seach)

ế

Ví d : Tìm tuy n tính

ụ

ế

Tìm nh phân (Binary Seach)

ị

Ý t

ng:

ưở

ph n t

đ u tiên c a dãy (L

ạ

ế

ầ ử ầ

eft

ừ ủ cu i cùng (Right = n)

ố

 So sánh giá tr X v i giá tr ph n t

gi a c a dãy A là

 Ph m vi tìm ki m là t = 1) cho đ n ph n t ầ ử ế ớ

ị

ầ ử ở ữ

ủ

ị

 N u X = A[Mid] Tìm th y ấ  N u X < A[Mid] rút ng n ph m vi tìm ki m và Right = ắ

ế

ạ

A[Mid] ế ế Mid –1

 N u X > A[Mid] rút ng n ph m vi tìm ki m và L ắ

ế

ạ

eft =

i quá trình cho đ n khi tìm th y ph n t

ầ ử

ế

ấ

có giá tr ị

ế Mid +1 ặ ạ

 L p l = X

Tìm nh phân (Binary Seach)

ị

ậ

ả

Thu t toán: B1: Left = 1; Right = n B2: Mid= (Left+ Right)/2 B3: so sánh A[Mid] v i X có 3 kh năng x y ra:  A[mid]=X; // tìm th y. D ng ừ  A[mid]>X; //Ti p t c tìm trong dãy A[1]… A[mid-1]

ớ ấ ế ụ

 A[mid]

Right=mid-1

ầ ử

ch a xét ư

ế ặ ạ

i B2 c l ượ ạ

B4: n u Left

i: K t thúc ế

Left=mid+1

Tìm nh phân (Binary Seach)

ị

Ví d :ụ X=8

Left=1, Right=8, Mid=4

1 2 4 5 6 8 12 15

X=8

1 2 4 5 6 8 12 15

Left=5, Right=8, Mid=6

X=8

1 4 5 6 8 15 2 12

Tìm nh phân (Binary Seach)

ệ ặ ậ

ị Cài đ t Thu t toán không đ quy Int BinarySearch( int A[], int n, int X) {

int left, right, mid; left=0; right=n-1; do {

mid=(left+right)/2 if(X==A[mid]) return(mid); if(X

} while(left<=right)

Return(-1); }

Tìm nh phân (Binary Seach)

ị

ặ

ậ

ệ

Cài đ t Thu t toán đ quy (Recursion Algorithm) int RecursiveBinarySearch (int A[], int Left, int Right, int X) { if (Left > Right) return (-1); int Mid = (Left + Right)/2; if (X == A[Mid]) return Mid; if (X < A[Mid])

return RecursiveBinarySearch (A, Left, Mid -1,X); return RecursiveBinarySearch (A, Mid +1, Right,X);

Tìm nh phân (Binary Seach)

ị

ậ

ợ ố ệ ầ ử ầ đ u tiên c a m ng có giá tr = X) ả ủ ị

min = 2

Phân tích, đánh giá thu t toán đ quy: t nh t (ph n t  Tr ấ min = 1

max = log2N +1

max =3log2N +1

avg = 1/2log2N +1

 S phép gán G  S phép so sánh S

ợ ấ ấ ầ ử nào c a m ng có giá ả ủ

avg = ½(3log2N + 3)

ng h p t ườ  S phép gán G ố  S phép so sánh S ố  Tr ng h p x u nh t (không có ph n t ườ tr = X) ị  S phép gán G ố  S phép so sánh S ố  Trung bình ố ố

Tìm nh phân (Binary Seach)

ị

ậ ệ

ế ế ạ

ự

ế

i v trí Mid i: Th c hi n B6 Thu t toán không đ quy (Non-Recursion Algorithm) B1: First = 1 B2: Last = N B3: N u (First > Last) // h t ph m vi tìm ki m ế Không tìm th yấ Th c hi n B8 ệ B4: Mid = (First + Last )/2 B5: N u (X = M[Mid]) Tìm th y t ấ ạ ị c l Ng ự ượ ạ ệ

B6: N u (X

Last = Mid –1 và L p l i B3 ặ ạ

i B3 ặ ạ

20 B7: N u (X>M[Mid]) First = Mid + 1 và l p l ế B8: K t thúc ế

Tìm nh phân (Binary Seach)

ị

ậ ặ ệ

Cài đ t Thu t toán không đ quy (Non-Recursion Algorithm) int NRBinarySearch (T M[], int N, T X) {

int First = 0; int Last = N-1; while (First <= Last) {

return Mid;

int Mid = (First + Last)/2; if (X == M[Mid]) if (X < M[Mid])

Last = Mid –1 ;

else

First = Mid + 1;

} return (-1);

21 }

Tìm nh phân (Binary Seach)

ị

ậ

ệ ủ ợ ố ị ầ ử ầ

min = 2

Phân tích, đánh giá thu t toán không đ quy: đ u tiên c a m ng có giá tr = X) t nh t (ph n t  Tr ả ấ min = 3

max = 2log2N +4

max =3log2N +1

avg = log2N +3.5

 S phép gán G  S phép so sánh S

ợ ấ ấ ầ ử nào c a m ng có giá ả ủ

avg = ½(3log2N + 3)

ng h p t ườ  S phép gán G ố  S phép so sánh S ố  Tr ng h p x u nh t (không có ph n t ườ tr = X) ị  S phép gán G ố  S phép so sánh S ố  Trung bình ố ố

2.3 Các gi

ả

i thu t tìm ki m ngo i ạ

ế

ậ

ả i thu t tìm ki m trên t p tin ế ậ ậ ạ ậ i thu t tìm ki m ngo i là gi ế

. Tìm xem có hay không ậ ầ ử

ị ế ầ ử có giá tr ị

 Các gi ả l u tr trên đĩa. ữ ư  Gi s có t p tin F l u tr N ph n t ả ử ư ph n t có giá tr X đ ầ ử X n m v trí nào trong t p tin F? ằ ở ị i thu t tìm ki m ngo i:  Xét 2 gi ạ ế ả

ữ c l u trong F. N u có ph n t ượ ư ậ

ậ

 Tìm tuy n tính  Tìm ki m theo ch m c (Index Search)

ế

ỉ ụ ế

2.3 Các gi

ả

i thu t tìm ki m ngo i ạ

ế

ậ

ầ ượ ọ t đ c các ph n trong t p ầ ậ

Tìm tuy n tính ế

tin X và so sánh v i giá tr X V i Ý t ớ ớ ng: L n l ưở ị

trong t p tin (read(F, a)) ậ

ư ≠ X và ch a h t t p tin (!eof(F)) ế ậ

Thu t toán: ậ B1: k = 0 B2: Tr v đ u t p tin (rewind(F)) ở ề ầ ậ B3: Đ c 1 ph n t ầ ử ọ B4: k = k + sizeof(T) B5: Ki m tra N u a ể ế i B3 L p l ặ ạ B6: IF N u a = X ế

có giá tr X t i v trí k bytes tính t đ u F Tìm th y ph n t ấ ầ ử ị ạ ị ừ ầ

B7: ELSE

Không tìm th y ph n t có giá tr X trong t p tin F ầ ử ấ ậ ị

B8: K t thúc ế

2.3 Các gi

ả

i thu t tìm ki m ngo i ạ

ế

ậ

ặ ậ

ế

Tìm tuy n tính (tt) Cài đ t Thu t toán: long FLinearSearch (char * FileName, T X) { FILE * Fp;

Fp = fopen(FileName, “rb”); if (Fp == NULL) return (-1); long k = 0; T a; int SOT = sizeof(T); while (!feof(Fp)) { if (fread(&a, SOT, 1, Fp) == 0) break;

k = k+ SOT; if (a == X) break; }

fclose (Fp); if (a == X) return (k - SOT); return (-1);

}

2.3 Các gi

ả

i thu t tìm ki m ngo i ạ

ế

ậ

Phân tích Thu t toán: ậ

ế

min = 2 + 1

t nh t (ph n t đ u tiên trong t p tin có giá tr = ậ ị ườ ợ ố ầ ử ầ

Tìm tuy n tính (tt) ng h p t  Tr ấ X)  S phép gán G  S phép so sánh S  S l n đ c t p tin D

min = 2 + 1 min = 1

 Tr

max = 2N + 2

nào trong t p tin có ọ ậ ấ ườ ấ ầ ử ậ

max = 2N +1 max = N

avg = ½(N +5)

ố ố ố ầ ng h p x u nh t (không có ph n t ợ giá tr = X) ị  S phép gán G ố  S phép so sánh S ố  S l n đ c t p tin D ố ầ ọ ậ

 S phép gán G  S phép so sánh S  S l n đ c t p tin D

 Trung bình ố ố ố ầ

avg = ½(N + 1) avg = ½(N + 1)

ọ ậ

2.3 Các gi

ả

i thu t tìm ki m ngo i ạ

ế

ậ

ướ ậ ể ớ

ậ ứ ữ ệ

ả

Tìm ki m theo ch m c (Index Search) ỉ ụ ế c t p tin có th l n (có th do các ph n t  Vì lý do kích th ầ ử ể ớ  Thao tác đ c t p tin trên d li u là ch a trong t p tin l n) ọ ậ lâu & không b o đ m an toàn d li u. ả th ữ ệ

ượ

ữ ệ  Đ giúp an toàn d li u, m t t p tin ệ ngườ đ ụ ề ỉ ụ

ộ ậ ể t p tin ch m c (Index File) làm nhi m v đi u khi n th t ậ xu t d li u trên t p tin theo m t  T p tin ch m c s ch a các ph n t g m 2 thành ph n t ng c đi kèm theo truy ứ ự ể ỉ ụ (Index Key). ầ ươ ộ khóa ch m c ầ ử ồ ậ ẽ ỉ ụ ứ

ấ ữ ệ ậ ng v i c u trúc DL: ớ ấ

ứ typedef struct IdxElement {

IdxKey;

T long Pos;

 T p tin ch m c luôn s p x p theo v trí tăng c a khóa ch ỉ ế

} IdxType

ỉ ụ ủ ắ ị

ậ m c.ụ

2.3 Các gi

ả

i thu t tìm ki m ngo i ạ

ế

ậ

ỉ ụ

ế ngưở

ớ

Tìm ki m theo ch m c (tt) Ý t Đ c t ị

ầ ử ỉ ụ v i giá ầ ử khóa ch m c có khóa ch m c >= giá tr X ỉ ụ ị

ọ

ượ ầ ử

đ u t p tin ch m c, so sánh ph n t ỉ ụ ọ ừ ầ ậ tr X cho đ n khi đ c đ n ph n t ế ọ ế hay đ c đ n cu i t p tin. ố ậ ế ế xu t t p tin F t N u trong quá trình trên tìm ki m đ ế ể ọ ấ ậ ạ ị c ph n t i v trí này đ đ c d li u, tránh m t th i gian. ữ ệ có giá tr = X, truy ị ờ ấ