Thuật Toán Interpolation Search - Tìm kiếm nội suy

1. Nguyên lý cơ bản của Interpolation Search

+ Cũng yêu cầu dãy số đầu vào là một dãy đã được xắp xếp cho sẵn.

+ Tìm kiếm nội suy là một sự cải tiến của tìm kiếm nhị phân Binary Search.

+ Nếu như tìm kiếm nhị phân luôn nhắm vào vị trí giữa của các khoảng tìm kiếm thì tìm kiếm nội suy lại có xu hướng tiến gần đến vị trí gần với giá trị tìm kiếm.

+ Do đó Tìm kiếm nội suy đạt được sự tối ưu rất cao, và tốc độ nhanh hơn nhiều Binary.

Độ phức tạp thời gian mà nó đạt được là: Log2(log2(n)).    (log cơ số 2)

Giả sử nếu số phần từ n = 1 tỷ

=> Linear O = 1 tỷ.

=> Binary O = log2(1 tỷ) xấp xỉ =  30

=> Nội suy O =  log2(log2(1 tỷ)) < 5

Các bạn sẽ thấy chỉ với số lượt nhỏ hơn 5, Tìm kiếm nội suy có thể tìm cho bạn được vị trí cần tìm trong 1 tỉ phần tử

=> RẤT KHỦNG.

Do đó nó được coi như hàng độc, và khi nào cần thiết thì mới sử dụng.

Vậy thì cơ chế nào để tìm kiếm nội suy có thể đạt được tốc độ kinh khủng như vậy.

Bí quyết của nó là tìm ra phần tử gần với giá trị tìm kiếm nhất và bắt đầu từ đó thể tìm.

Ví dụ bạn có 1 danh sách tập hợp các thành viên trong một công ty đã xắp xếp theo thứ tự a – b- c

Giả sử chúng ta cần tìm người tên là Tài, thì chúng ta sẽ ưu tiên việc tìm từ cuối danh sách chứ không dại gì mò từ đầu danh sách.

Suy ra chúng ta phải tìm được phần tử cuối danh sách mà gần với phần tử tìm kiếm tên Tài.

Giả sử ta có: left , right là hai vị trí đầu cuối, T là tập, X là giá trị cần tìm.

Step 1:

Bắt đầu từ công thức tìm phần từ chính giữa của tập theo Binary Search ta có

pos = left + (right – left)* 1/2;

Ta sẽ cải tiến bằng cách thay giá trị 1/2 bằng biểu thức sau:  (X – T[left])/(T[right] – T[left])

Như vậy pos = left + (X- T[left]) * (right – left) / (T[right] – T[left])

Pos chính là vị trí dò tìm được mà nó khá gần so với giá trị X cần tìm.

Step 2:

Kiểm T[pos] nếu bằng X thì pos là vị trí cần tìm.

Nếu nhỏ hơn X thì ta tăng left lên một đơn vị và tiếp tục thực hiện lại bước 1

Nếu lớn hơn X thì ta giảm right một đơn vị và tiếp tục thực hiện lại bước 1
(Ở bước này thì làm như giải thuật Binary Search)

2. Cài đặt Interpolation Search

Bây giờ từ nguyên lý ở trên chúng ta sẽ cùng thực hành với code c++

Hàm InterpolationSearch.

#include <iostream>
using namespace std;
int n, a[100], res = -1, key;
int Interpolation_Search(int key)
{
 int lo = 0, hi = n - 1; // set 2 vi tri dau va cuoi
 while(lo <= hi) 
 {
  int mid = lo + (hi - lo)/(a[hi] - a[lo]) * (key - a[lo]);
  if (a[mid] > key) hi = mid - 1;
  else if (a[mid] < key) lo = mid + 1;
  else return mid;
 }
 return res;
}

Hàm Main.

int main()
{
 cin >> n; 
 for (int i = 0; i < n; i++) 
 {
  cout << "a[" << i << "]:"; cin >> a[i];
 }
 
        cout << "Key: ";
        cin >> key;
        
        int pos = Interpolation_Search(key);
 if (pos > -1) cout << "Tim thay tai vi tri: " << pos;
 else cout << "Khong ton tai";
}



Input:
5
a[0]: 1
a[1]: 5
a[2]: 7
a[3]: -5
a[4]: 10
Key: 10


Output:
Tim thay tai vi tri 4






Cảm ơn các bạn đã theo dõi.