Chương 2.1. Giải thuật tìm kiếm

ầ

Tr n Minh Thái Email: minhthai@huflit.edu.vn Website: www.minhthai.edu.vn

1

Mục tiêu

• Xác định được vai trò của tìm kiếm và sắp xếp trong hệ thống

thông tin

• Nắm vững và minh họa được giải thuật tìm kiếm tuyến tính và

tìm kiếm nhị phân trên mảng một chiều

• Cài đặt được giải thuật tìm kiếm bằng ngôn ngữ C#

2

Nhu cầu tìm kiếm và sắp xếp

• Tìm kiếm: Có trong hầu hết trong các hệ thống thông tin

• Muốn tìm kiếm nhanh và hiệu quả  dữ liệu có thứ tự  sắp

xếp

3

Vấn đề tìm kiếm

• Dựa vào một phần thông tin được gọi là khoá (key)  tìm một

mẫu tin (record) chứa các thông tin khác liên quan với khoá này

• Có thể có nhiều mẫu tin hoặc không có mẫu tin nào chứa

khoá cần tìm

4

Đánh giá giải thuật tìm kiếm

• Tìm kiếm thường là tác vụ tốn nhiều thời gian trong một

chương trình

 Tổ chức cấu trúc dữ liệu và giải thuật cho việc tìm kiếm ảnh

hưởng lớn đến hiệu suất hoạt động của chương trình

• Thông số đo chủ yếu là số lần so sánh khoá cần tìm với các

mẫu tin khác

5

Phân loại

• Tìm kiếm nội và tìm kiếm ngoại

• Dữ liệu lưu trên thiết bị lưu trữ ngoài như đĩa hay băng từ: tìm

kiếm ngoại

• Dữ liệu được lưu trữ trên bộ nhớ chính: tìm kiếm nội

6

Các giải thuật tìm kiếm trên dãy

• Có 2 giải thuật thường được áp dụng: Tìm tuần tự và tìm nhị

phân

• Đặc tả:

a3 a4

a2

a5

…

aN

a1 • Tập dữ liệu được lưu trữ là dãy số a1, a2, ... ,aN.

an- 1

• Khai báo: int []a = new int[N];

• Khóa cần tìm: int x;

7

Tìm kiếm tuần tự (Linear Search)

Ý tưởng

Lần lượt so sánh x 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ần tìm, hoặc hết mảng

8

Tìm kiếm tuần tự

• Minh họa tìm x =10

10

Đã tìm Chưa hết thấy tại mảng vị trí 5

12 3

7 1

10 10 5

32 6

13 7

9 8

15 9

3 10

41 5 4 2 • Minh họa tìm x =25

25

Đã hết Chưa hết mảng mảng

7 1

5 2

12 3

41 4

10 5

32 6

13 7

9 8

15 9

3 10

9

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. 10

Nguyên tắc cài đặt hàm tìm kiếm

• Nếu có xuất hiện phần tử có giá trị x thì trả về vị trí tìm được

• Ngược lại thì trả về -1

11

Cài đặt int LinearSearch(int []a, int N, int x)

{

int i=0;

while ((i

i++;

if(i==N)

return -1; //tìm hết mảng

else

return i; //a[i] là phần tử có khoá x

12

}

Bài tập 1

Thiết kế và định nghĩa lớp CMyIntArray chứa mảng số nguyên.

Gồm các phương thức phát sinh, xuất, tìm kiếm tuần tự và cho

biết số lần so sánh (code C#)

13

Cải tiến

Dùng lính canh giúp giảm bớt phép so sánh

• Minh họa tìm x =10

10

10

12 3

7 1

10 10 5

32 6

13 7

15 9

3 10

9 8

11

41 5 4 2 • Minh họa tìm x = 25

25

5 2

12 3

41 4

10 5

32 6

13 7

3 10

15 9

7 1

9 8

25 25 11

14

Cài đặt int LinearSearch2(int []a,int N,int x) {

int i=0;

a[N] = x; // thêm phần tử x sau mảng  while (a[i]!=x ) i++;

return -1; // tìm hết mảng

if (i==N)   else

return i;  // tìm thấy x tại vị trí i

}  Độ phức tạp tính toán cấp n: T(n)=O(n)

15

Bài tập 2

Bổ sung phương thức tìm tuần tự cải tiến vào lớp CMyIntArray.

Tiến hành so sánh (về số lần so sánh) của 2 phương pháp tìm

kiếm vừa được đề cập

16

Q & A

17

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

Ý tưởng

• Áp dụng đối với dãy số đã có thứ tự

• Mỗi bước tiến hành so sánh x với phần tử ở giữa của dãy hiện

hành để quyết định phạm vi tìm kế tiếp

18

Minh họa tìm x = 41

14 14 14 14

16 16 16 16

19 19 19 19

41 41 41 41

46 46 46 46

63 63 63 63

3 3 3 3

22 22 22 22

51 51 51 51

71 71 71 71

2 2 2 2

3 3 3 3

4 4 4 4

6 6 6 6

7 7 7 7

9 9 9 9

1 1 1 1

5 5 5 5

8 8 8 8

10 10 10 10

x x x

Tìm thấy x tại vị trí 6 l m m r

m

19

Minh họa tìm x = 45

14 14 14 14 14

16 16 16 16 16

19 19 19 19 19

41 41 41 41 41

46 46 46 46 46

63 63 63 63 63

3 3 3 3 3

22 22 22 22 22

51 51 51 51 51

71 71 71 71 71

2 2 2 2 2

3 3 3 3 3

4 4 4 4 4

6 6 6 6 6

7 7 7 7 7

9 9 9 9 9

1 1 1 1 1

5 5 5 5 5

8 8 8 8 8

10 10 10 10 10

x x x x

l m m r

l > r: Kết thúc: Không tìm thấy

m

m

20

Giải thuật Bước 1: left = 1; right = N; //tìm kiếm tất cả các phần tử Bước 2: mid = (left+right)/2; // lấy mốc so sánh So sánh a[mid] với x, có 3 khả năng : • a[mid] = x: Tìm thấy. Dừng • a[mid] > x:

//tìm tiếp x trong dãy con aleft .. amid -1

right =mid - 1;

• a[mid] < x:

//tìm tiếp x trong dãy con amid +1 .. aright

left = mid + 1;

Bước 3:

Nếu left <= right //còn phần tử chưa xét tìm tiếp.

Lặp lại Bước 2.

Ngược lại: Dừng //Ðã xét hết tất cả các phần tử.

21

int BinarySearch(int []a, int N, int x )

{

int left =0; right = N-1;

int mid; while (left <= right) {

mid = (left + right)/2;

if (x == a[mid])

return mid;//Thấy x tại mid

if (x < a[mid])

right = mid -1;

else left = mid +1;

}

return -1; // Tìm hết dãy mà không có x

}

Độ phức tạp tính toán cấp n: T(n)=O(log 2n)

22

Q & A

23

Bài tập 3

Bổ sung vào lớp CMyIntArray:

• Phương thức phát sinh dãy số tăng dần, tiến hành so sánh (về

số phép so sánh) của hai phương pháp tìm kiếm tuần tự và nhị

phân

• Phương thức kiểm tra xem dãy số có thứ tự tăng/ giảm/ không

có thứ tự để áp dụng phương pháp tìm kiếm nhị phân hay tuần

tự cho phù hợp

24

Bài tập lý thuyết

• LT1_1: Cho dãy số sau:

3 1

4 2

6 3

6 4

12 5

16 6

21 7

34 8

41 9

80 10

Cho biết vị trí tìm thấy và số lần so sánh để tìm được phần tử có giá trị x = 6 khi áp dụng giải thuật tìm kiếm: tuyến tính và nhị phân

• LT1_2: Xây dựng giải thuật tìm kiếm phần tử có giá trị nhỏ nhất

trong dãy số: Dùng mã tự nhiên, mã giả và lưu đồ

25

Q & A

26