Thuật toán tìm kiếm Tam Phân
Bùi Văn Tân
Tìm kiếm là một yêu cầu rất thường xuyên trong đời sống hàng ngày. Trong tin học nó đặt
nền móng cho nhiều tác vụ tính toán quan trọng. Bài toán tìm kiếm là sự xác định vị trí của
một hay nhiều phần tử, gọi là đối trị tìm kiếm (Argument), trong một bảng liệt kê có thứ tự
các phần tử. Mỗi phần tử đơược đại diện bằng một khoá (Key) phục vụ cho tìm kiếm.
Những ứng dụng của tìm kiếm thì rất đa dạng, cũng như có rất nhiều các thuật toán với đặc
trương và hiệu suất khác nhau. Một trong những phơương pháp khá hiệu quả là phương
pháp tìm kiếm Tam Phân.
Thuật toán tìm kiếm Tam Phân (Trisearch), xác định vị trí của phần tử cần tìm trong một
bảng lệt kê các phần tử đươợc sắp xếp theo thứ tự tăng (hay giảm) dần của trường khoá.
Bằng cách chia liên tiếp bảng liệt kê thành ba bảng liệt kê con có kích thơước tương
đươơng nhau (Step=(R-L+1) div 3). Thuật toán này là sự thể hiện sinh động của tinh thần
“chia để trị”. Giả sử bảng liệt kê đơược xác định bởi hai con trỏ L,R, trỏ đến phần tử trái
và phải. Thuật toán sẽ chia bảng [L,R] thành ba bảng con: [L,U-1], [Ư1,V-1], [V+1,R].
Dựa vào giá trị khoá của Argument và giá trị khoá tại các điểm U=Step , V=L+2*Step.
Tìm kiếm sẽ dừng nếu khoá của mẫu bằng với giá trị khoá của một trong hai điểm trên,
ngược lại tìm kiếm sẽ tiếp tục trên một trong ba bảng con đơược chia. Quá trình cứ tiếp tục
nhươ thế cho đến khi tìm đươợc phần tử mong muốn hoặc bảng phần tử đang sét là rỗng.
Hình 1 mô tả hình thức tam phân của Trisearch theo sơ đồ “chia để trị”.
Thuật toán sau đây đơược trình bày đưới dạng giả mã, sẽ tìm kiếm phần tử Item trong
mảng Key đã được sắp xếp theo thứ tự tăng dần:
int Trisearch(int key[], int item, int l, int r)
{
int u, v, result, step;
result=0;
while ((l<=r) && (result==0))
{
step =(r-l+1) / 3;
u=l+step; v=l+2*step;
if (item == key[u] ) result=u;

return Trisearch_dq(key, item,v+1,r);
else+
if (item > key[u] )
return Trisearch_dq(key, item,ư1,v-1);
else
return Trisearch_dq(key, item,l,u-1);
}
else /*khong thanh cong*/
return 0;
}
Khi nói đến các thuật toán tìm kiếm, chúng ta sẽ cảm thấy quen thuộc hơn với thuật toán
tìm kiếm nhị phân (Binsearch). Có lẽ bởi tính tự nhiên của phương pháp và dễ cài đặt của
thuật toán. Binsearch có độ phức tạp thuật toán về thời gian là O(log
2
n). Vậy hiệu quả của
Trisearch so với Binsearch? Dễ nhận thấy rằng so với Binsearch thì thuật toán Trisearch
trong cài đặt đệ quy sẽ hội tụ nhanh hơn, hạn chế khả năng đệ quy sâu. Sau đây chúng ta sẽ
phân tích độ phức tạp thuật toán về thời gian của Trisearch.
Không giảm tính tổng quát, ta giả thiết phạm vi tìm kiếm là từ 1 đến N, bảng key có N
phần tử. Sau lần lặp thứ nhất phạm vi tìm kiếm là phần tử, sau lần lặp thứ 2 phạm vi tìm
kiếm là N/3. Trong trường hợp tồi nhất vòng lặp While sẽ kết thúc khi N/3
i
=1, hay I =
Log
3
n. Trong mỗi lần lặp tốn thời gian O(1) nên thời gian thực hiện của hàm Trisearch là
O(log
3
n). Dễ nhận thấy rằng Binsearch và Trisearch có cùng độ phức tạp, hay O(log
3