TS. Lê Minh Trung ThS Lương Trần Ngọc Khiết Khoa CNTT, Đại học Sư phạm, TP. HCM

Nội dung

 Giới thiệu bài toán tìm kiếm  Tìm kiếm tuần tự  Tìm kiếm nhị phân

Khái niệm tìm kiếm

 Cho biết:

 Một danh sách các bản ghi (record).  Một khóa cần tìm.

 Tìm bản ghi có khóa trùng với khóa cần tìm (nếu có).  Đo độ hiệu quả:

 Số lần so sánh khóa cần tìm và khóa của các bản ghi

 Phân loại:

 Tìm kiếm nội (internal searching)  Tìm kiếm ngoại (external searching)

Tìm kiếm tuần tự  Input: mảng đầu vào int a[n], khóa cần tìm key  Output: vị trí tìm thấy đầu tiên của key trong mảng

hoặc -1 nếu không tìm thấy

int SequentialSearch(int a[n], int key) {

for(int i=0; i

}

Tìm tuần tự (sequential search)

position = 2

5

Target key

return success

Số lần so sánh: 3

0 7 1 13 2 5 4 3 21 6 5 2 7 6 8 15

Tìm tuần tự - không tìm thấy

9

Target key

return not_present

Số lần so sánh: 8

0 7 1 13 2 5 4 3 21 6 5 2 7 6 8 15

Phân tích tìm kiếm tuần tự  Không tìm thấy:

 Số phép so sánh: SS=n

 Tìm thấy:

 Tốt nhất (a[0]=key): SS=1  Xấu nhất (a[n-1]=key): SS=n  Trung bình

𝑛−1 𝑖 + 1 𝑃 𝑘𝑒𝑦 = 𝑎 𝑖 =

𝑛 𝑖 =

=

= 𝑂(𝑛)

 𝑆𝑆 = 𝑖=0

𝑖=1

1 𝑛

𝑛(𝑛+1) 2𝑛

𝑛+1 2

Tìm kiếm nhị phân

 Dùng trong trường hợp mảng đầu vào đã được sắp thứ

tự

 Ý tưởng:

 So sánh khóa cần tìm với phần tử giữa.  Nếu nó nhỏ hơn thì tìm bên trái mảng.  Ngược lại tìm bên phải mảng.  Lặp lại động tác này.

 Cần 2 chỉ mục left và right để giới hạn đoạn tìm kiếm

trên mảng.

 Khóa cần tìm nếu có chỉ nằm trong đoạn này.

Tìm kiếm nhị phân  Input: mảng tăng int a[n], khóa cần tìm key  Output: vị trí tìm thấy đầu tiên của key trong mảng

hoặc -1 nếu không tìm thấy

int BinarySearch(int a[], int n, int key){

int left=0, right=n-1,middle; while(left<=right){

middle = (left+right)/2; if(a[middle]==key)return middle; if(key

} return -1;

}

Tìm nhị phân

position = 3

Khóa cần tìm bằng Khóa cần tìm không bằng Khóa cần tìm lớn hơn Khóa cần tìm nhỏ hơn

10 Target key

3 4 7 8

left

middle

right

return success

Số lần so sánh: 7

0 2 1 5 5 2 8 10 12 13 9 6 15 18 21 24

Phân tích tìm kiếm nhị phân

 Số lần lặp không vượt quá 𝑙𝑜𝑔2𝑛  Trong mỗi vòng lặp sử dụng tối đa hai phép so sánh  Số phép so sánh tối đa 2 𝑙𝑜𝑔2𝑛  Độ phức tạp của thuật toán: 𝑂 𝑙𝑜𝑔2(𝑛)