C++: Tìm kiếm tam phân (Ternary Search)

Tổng quan

Tìm kiếm bậc ba là một thuật toán giảm (theo hằng số) và chinh phục có thể được sử dụng để tìm một phần tử trong một mảng . Nó tương tự như tìm kiếm nhị phân trong đó chia mảng thành hai phần nhưng trong thuật toán này, chia mảng đã cho thành ba phần và xác định phần nào có khóa (phần tử được tìm kiếm)

Lưu ý: Mảng cần được sắp xếp để thực hiện tìm kiếm bậc ba trên đó.

Cách thức triển khai thuật toán như sau:

Chia mảng thành ba phần bằng cách lấy mid1 và mid2 có thể được tính như dưới đây. Ban đầu, l và r sẽ lần lượt bằng 0 và n-1, trong đó n là độ dài của mảng

mid1 = l + (r-l)/3 
mid2 = r – (r-l)/3 

1. Đầu tiên, chúng ta so sánh khóa với phần tử ở mid1. Nếu tìm thấy bằng nhau, chúng tôi trả về mid1.
2. Nếu không, chúng ta so sánh khóa với phần tử ở mid2. Nếu tìm thấy bằng nhau, chúng tôi trả về mid2.
3. Nếu không, chúng tôi sẽ kiểm tra xem khóa có nhỏ hơn phần tử ở mid1 hay không. Nếu có thì quay lại phần đầu tiên [l;mid1)
4. Nếu không, chúng tôi sẽ kiểm tra xem khóa có lớn hơn phần tử ở mid2 hay không. Nếu có thì quay lại tìm kiếm ở phần thứ ba (mid2; r]
5. Nếu không, chúng ta quay lại phần thứ hai (mid1;mid2).

Nhận xét: 

Tương tự với tìm kiếm nhị phân. Sự khác biệt duy nhất là nó làm giảm độ phức tạp về thời gian hơn một chút. thuật toán bao 'N' bước. Phạm vi có thể tìm kiếm sẽ là 3^N. Ngược lại, số bước cần thiết để tìm phần tử là log3 kích thước của mảng. Vì vậy thời gian chạy là O (log3(N)).
Độ phức tạp về thời gian cho tìm kiếm bậc ba trung bình là O (log3(N)).
Độ phức tạp về thời gian trong trường hợp tốt nhất là O(1) và độ phức tạp trong trường hợp xấu nhất là O (log3(N)).

Ví dụ: 

#include <bits/stdc++.h>
using namespace std;
 
int ternarySearch(int l, int r, int key, int ar[])
{
    if (r >= l) {
 
        // tìm mid1 và mid2
        int mid1 = l + (r - l) / 3;
        int mid2 = r - (r - l) / 3;
 
        // kiểm tra giá trị của mảng tại vị trí mid1 và mid2
        if (ar[mid1] == key) {
            return mid1;
        }
        if (ar[mid2] == key) {
            return mid2;
        }
 
        // key không nằm ở vị trí mid1 hoặc mid2
        if (key < ar[mid1]) {
 
            // key nằm trong khoảng l đến mid1-1
            return ternarySearch(l, mid1 - 1, key, ar);
        }
        else if (key > ar[mid2]) {
 
            //  key nằm trong khoảng mid2+1 đến r
            return ternarySearch(mid2 + 1, r, key, ar);
        }
        else {
 
            // key nằm trong khoảng mid1+1 và mid2-1
            return ternarySearch(mid1 + 1, mid2 - 1, key, ar);
        }
    }
 
    // Không tìm thấy
    return -1;
}
 
int main()
{
    int l, r, p, key;
    // mảng đã sắp xếp
    int ar[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
 
    l = 0;
    r = 9;
 
    // key
    key = 5;
 
    // sử dụng tìm kiếm tam phân
    p = ternarySearch(l, r, key, ar);
     
    // in kết quả
    cout << "Index of " << key
         << " is " << p << endl;
 
    // Key 
    key = 50;
 
    // sử dụng tìm kiếm tam phân
    p = ternarySearch(l, r, key, ar);
    // In kết quả
    cout << "Index of " << key
         << " is " << p << endl;
}