Cấu trúc dữ liệu chương 2 b Tìm kiếm

3. Các phương pháp tìm kiếm nội

Có 2 giải thuật thường được áp dụng để tìm kiếm dữ liệu là tìm tuyến tính và tìm nhị phân

3.1 Tìm kiếm tuyến tính

Giải thuật
Tìm tuyến tính là một kỹ thuật tìm kiếm rất đơn giản và cổ điển. Thuật toán tiến hành so sánh x lần lượt 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ó khóa cần tìm, hoặc đã tìm hết mảng mà không thấy x. Các bước tiến hành như sau :
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.
Ví dụ : cho dãy số a: 12 2 8 5 1 6 4 15
Nếu giá trị cần tìm là 8, giải thuật được tiến hành như sau :
Hình 2.2
i = 1
Hình 2.3
i = 2
i = 3 Dừng

Cài đặt
Từ mô tả trên đây của thuật toán tìm tuyến tính , có thể cài đặt hàm LinearSearch để xác định vị trí của phần tử có khoá x trong mảng a :

int LinearSearch(int a[], int N, int x)
{ int i=0;
while ((i<N) && (a[i]!=x )) i++;
if(i==N) return -1; // tìm hết mảng nhưng không có x
else return i; // a[i] là phần tử có khoá x
}

Trong cài đặt trên đây, nhận thấy mỗi lần lặp của vòng lặp while phải tiến thành kiểm tra 2 điều kiện (i<N) - điều kiện biên của mảng - và (a[i]!=x )- điều kiện kiểm tra chính. Nhưng thật sự chỉ cần kiểm tra điều kiện chính(a[i] !=x), để cải tiến cài đặt, có thể dùng phương pháp "lính canh" - đặt thêm một phần tử có giá trị x vào cuối mảng, như vậy bảo đảm luôn tìm thấy x trong mảng, sau đó dựa vào vị trí tìm thấy để kết luận. Cài đặt cải tiến sau đây của hàm LinearSearch giúp giảm bớt một phép so sánh trong vòng lặp :

int LinearSearch(int a[],int N,int x)
{ int i=0; // mảng gồm N phần tử từ a[0]..a[N-1]
a[N] = x; // thêm phần tử thứ N+1
while (a[i]!=x ) i++;
if (i==N)
return -1; // tìm hết mảng nhưng không có x
else
return i; // tìm thấy x tại vị trí i
}

Ðánh giá giải thuật
Có thể ước lượng độ phức tạp của giải thuật tìm kiếm qua số lượng các phép so sánh được tiến hành để tìm ra x. Trường hợp giải thuật tìm tuyến tính, có:
Trường hợp Số lần so sánh Giải thích
Tốt nhất 1 Phần tử đầu tiên có giá trị x
Xấu nhất n+1 Phần tử cuối cùng có giá trị x
Trung bình (n+1)/2 Giả sử xác suất các phần tử trong mảng nhận giá trị x là như nhau.
Vậy giải thuật tìm tuyến tính có độ phức tạp tính toán : T(n) = O(n)

Nhận xét

• Giải thuật tìm tuyến tính không phụ thuộc vào thứ tự của các phần tử mảng, do vậy đây là phương pháp tổng quát nhất để tìm kiếm trên một dãy số bất kỳ.
• Một thuật toán có thể được cài đặt theo nhiều cách khác nhau, kỹ thuật cài đặt ảnh hưởng đến tốc độ thực hiện của thuật toán.

3.2 Tìm kiếm nhị phân

Giải thuật
Ðối với những dãy số đã có thứ tự ( giả sử thứ tự tăng ), các phần tử trong dãy có quan hệ ai -1 £ ai £ ai+1, từ đó kết luận được nếu x > ai thì x chỉ có thể xuất hiện trong đoạn
[ai+1 ,aN] của dãy , ngược lại nếu x < ai thì x chỉ có thể xuất hiện trong đoạn [a1 ,ai-1] của dãy . Giải thuật tìm nhị phân áp dụng nhận xét trên đây để tìm cách giới hạn phạm vi tìm kiếm sau mỗi lần so sánh x với một phần tử trong dãy. Ý tưởng của giải thuật là tại mỗi bước tiến hành so sánh x với phần tử nằm ở vị trí giữa của dãy tìm kiếm hiện hành, dựa vào kết quả so sánh này để quyết định giới hạn dãy tìm kiếm ở bước kế tiếp là nửa trên hay nửa dưới của dãy tìm kiếm hiện hành. Giả sử dãy tìm kiếm hiện hành bao gồm các phần tử aleft .. aright , các bước tiến hành như sau :

Bước 1: left = 1; right = N; // tìm kiếm trên 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 =midle - 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ử.
Ví dụ : Cho dãy số a gồm 8 phần tử:
1 2 4 5 6 8 12 15

Nếu giá trị cần tìm là 8, giải thuật được tiến hành như sau:
left = 1, right = 8, midle = 4

left = 5, right = 8, midle = 6 Dừng

Cài đặt
Thuật toán tìm nhị phân có thể được cài đặt thành hàm BinarySearch:

int BinarySearch(int a[],int N,int x )
{ int left =0; right = N-1;
int midle;
do {
mid = (left + right)/2;
if (x = a[midle]) return midle;//Thấy x tại mid else
if (x < a[midle]) right = midle -1;
else left = midle +1;
}while (left <= right);
return -1; // Tìm hết dãy mà không có x
}

Ðánh giá giải thuật
Trường hợp giải thuật tìm nhị phân, có bảng phân tích sau :
Trường hợp Số lần so sánh Giải thích
Tốt nhất 1 Phần tử giữa của mảng có giá trị x
Xấu nhất log 2 n Không có x trong mảng
Trung bình log 2 (n/2) Giả sử xác suất các phần tử trong mảng nhận giá trị x là như nhau
Vậy giải thuật tìm nhị phân có độ phức tạp tính toán : T(n) = O(log 2 n)

Nhận xét

• Giải thuật tìm nhị phân dựa vào quan hệ giá trị của các phần tử mảng để định hướng trong quá trình tìm kiếm, do vậy chỉ áp dụng được cho những dãy đã có thứ tự.

• Giải thuật tìm nhị phân tiết kiệm thời gian hơn rất nhiều so với giải thuật tìm tuyến tính do Tnhị phân (n) = O(log2n) <>

Tuy nhiên khi muốn áp dụng giải thuật tìm nhị phân cần phải xét đến thời gian sắp xếp dãy số để thỏa điều kiện dãy số có thứ tự. Thời gian này không nhỏ, và khi dãy số biến động cần phải tiến hành sắp xếp lại . Tất cả các nhu cầu đó tạo ra khuyết điểm chính cho giải thuật tìm nhị phân. Ta cần cân nhắc nhu cầu thực tế để chọn một trong hai giải thuật tìm kiếm trên sao cho có lợi nhất