Xem mẫu
Đ i H c S Ph m Tp. H Chí Minh Tìm kim & Sp xp
Muïc tieâu:
C U TRÚC D LI U 1
• Giôùi thieäu moät soá thuaät toaùn tìm kieám vaø saép xeáp noäi.
• Phaân tích, ñaùnh giaù ñoä phöùc taïp cuûa caùc giaûi thuaät tìm kieám, saép xeáp.
Noäi dung:
Chng 2: Tìm kim & Sp xp
• Nhu caàu tìm kieám vaø saép xeáp döõ lieäu trong moät heä thoáng thoâng tin.
• Caùc giaûi thuaät tìm kieám noäi.
• Caùc giaûi thuaät saép xeáp noäi.
2
Tìm kim
• Tìm tuần tự
Caùc giaûi thuaät tìm kieám noäi
Caùc giaûi thuaät tìm kieám noäi
Baøi toaùn: Tìm vò trí xuaát hieän cuûa phaàn töû coù giaù trò x treân danh saùch ñaëc a
•Taäp döõ lieäu ñöôïc löu tröõ laø daõy soá a1, a2, ... ,aN int a[N];
•Khoaù caàn tìm laø x
int x;
3 4
Tìm kieám tuaàn töï Tìm kieám tuaàn töï
• Böôùc 1: i = Vò trí ñaàu; • Ví duï: Cho daõy soá a
• Böôùc 2: Neáu a[i] = x : Tìm thaáy. Döøng, vò trí 12 2 8 5 1 6 4 15
xuaát hieän: i
• Böôùc 3 : i = Vò trí keá(i);// xeùt tieáp phaàn töû keá trong maûng
• Böôùc 4: Neáu i >Vò trí cuoái: //Heát maûng Khoâng tìm thaáy. Döøng.
Ngöôïc laïi: Laëp laïi Böôùc 2.
5
• Giaù trò caàn tìm: 8
• i = 1
6
Tìm kieám tuaàn töï Tìm kieám tuaàn töï
• i = 2 int LinearSearch(int a[], int N, int x) {
for (int i=0; (i a thì x chæ coù theå xuaát hieän trong ñoaïn [ai+1 ,aN] cuûa daõy
Neáu x < a thì x chæ coù theå xuaát hieän trong ñoaïn [a1 ,ai-1] cuûa daõy
13
Tìm kieám nhò phaân
haønh so saùnh x vôùi phaàn töû naèm ôû vò trí giöõa cuûa daõy tìm kieám hieän haønh, döïa vaøo keát quaû so saùnh naøy ñeå quyeát ñònh giôùi haïn daõy tìm kieám ôû böôùc keá tieáp laø nöûa treân hay nöûa döôùi cuûa daõy tìm kieám hieän haønh
14
Tìm kieám nhò phaân
Böôùc 1: left = VTÑ; right = VTC;
Böôùc 2: Trong khi left £ right laëp: //ñoaïn tìm kieám chöa roãng Böôùc 2.1: mid = (left+right)/2; // laáy moác so saùnh
Böôùc 2.2: Neáu a[mid] = x: //Tìm thaáy. Döøng, vò trí xuaát hieän: mid
Böôùc 2.3: Neáu a[mid] > x: //tìm x trong daõy con aleft .. amid -1 right = mid - 1;
• Ví duï: Cho daõy soá a goàm 8 phaàn töû:
1 2 4 5 6 8 12 15
• Giaù trò caàn tìm laø 8
Ngöôïc laïi //tìm x trong daõy con amid +1 .. aright left = mid + 1;
//Heát laëp
Böôùc 3: Döøng, khoâng tìm thaáy.
15 16
Tìm kieám nhò phaân
• left = 1, right = 8, mid = 4
Tìm kieám nhò phaân
• left = 5, right = 8, mid = 6
17 18
Tìm kieám nhò phaân Tìm kieám nhò phaân
int BinarySearch(int a[],int N,int x ) {
int left =0, right = N-1, midle; while (left <= right)
{
midle = (left + right)/2; if (x == a[midle])
return midle;//Tìm thaáy x taïi mid if (x
nguon tai.lieu . vn