CTDL và giải thuật

Giải thuật Tìm kiếm nội suy (Interpolation Search) là gì ?

Tìm kiếm nội suy (Interpolation Search) là biến thể cải tạo của Tìm kiếm nhị phân (Binary Search). Để giải thuật tìm kiếm này làm việc đúng đắn thì tập dữ liệu phải được sắp đặt.

Binary Search có ích thế lớn về độ cầu kỳ thời gian khi so sánh với Linear Search. Linear Search có độ cầu kỳ trường hợp xấu đặc biệt là Ο(ɳ) trong lúc Binary Search là Ο(log ɳ).

Có một số tình huống mà địa điểm của dữ liệu cần tìm có thể đã được biết trước. Chẳng hạn, trong trường hợp danh bạ smartphone, nếu tất cả chúng ta mong muốn tìm số smartphone của Hương ví dụ. Trong trường hợp này, Linear Search và cả Binary Search có thể là chậm khi thực hiện tìm kiếm, khi mà tất cả chúng ta có thể trực tiếp nhảy tới phần không gian bộ nhớ lưu trữ có tên khởi đầu với Н được giữ lại.

Xác nhận địa điểm trong Binary Search

Trong Binary Search, nếu dữ liệu cần tìm không được tìm ra thì phần còn sót lại của danh mục được phân tách thành hai phần: phần bên trái (chứa giá trị bé hơn) và phần bên phải (chứa giá trị to hơn). Sau đó công cuộc tìm kiếm được thực hiện trên một trong hai phần này.

 

Dò địa điểm trong Tìm kiếm nội suy (Interpolation Search)

Tìm kiếm nội suy tìm kiếm một phần tử rõ ràng và cụ thể bằng việc tính toán địa điểm dò (Probe Position). Ban đầu thì địa điểm dò là địa điểm của phần tử nằm ở giữa nhất của tập dữ liệu.

Xem Thêm  HTTP Headers Explained - http header

Giải thuật Tìm kiếm nội suy (Interpolation Search)

Nếu tìm ra connect thì chỉ mục của phần tử được trả về. Để chia danh mục thành hai phần, tất cả chúng ta sử dụng bí quyết sau:

mid = Lo + ((Hi - Lo) / (?[Hi] - ?[Lo])) * (Ҳ - ?[Lo])

Trong số đó:
   ?    = danh mục
   Lo   = chỉ mục thấp nhất của danh mục
   Hi   = chỉ mục cao nhất của danh mục
   ?[n] = giá trị được giữ lại tại chỉ mục ɳ trong danh mục

Nếu phần tử cần tìm có giá trị to hơn phần tử ở giữa thì phần tử cần tìm sẽ ở mảng con bên phải phần tử ở giữa và tất cả chúng ta lại tiếp tục tính địa điểm dò; còn nếu không phần tử cần tìm sẽ ở mảng con bên trái phần tử ở giữa. Công cuộc này tiến tụp diễn ra trên các mảng con cho tới khi kích thước của mảng con giảm về 0.

Độ cầu kỳ thời gian chạy của Interpolation Search là Ο(log (log ɳ)), trong lúc của Binary Search là Ο(log ɳ).

Giải thuật Tìm kiếm nội suy

Bởi vì đây là sự cải tạo của giải thuật Binary Search nên tất cả chúng ta sẽ chỉ đề cập tới các bước để tìm kiếm chỉ mục của giá trị cần tìm bởi sử dụng địa điểm dò.

Bước 1 : Khởi đầu tìm kiếm dữ liệu từ phần giữa của danh mục
Bước 2 : Nếu đây là một so khớp (một connect), thì trả về chỉ mục của phần tử, và thoát.
Bước 3 : Còn nếu như không phải là một so khớp, thì là địa điểm dò.
Bước 4 : Chia danh mục bởi sử dụng phép tính tìm địa điểm dò và tìm địa điểm giữa mới.
Bước 5 : Nếu dữ liệu cần tìm to hơn giá trị tại địa điểm giữa, thì tìm kiếm trong mảng con bên phải.
Bước 6 : Nếu dữ liệu cần tìm bé hơn giá trị tại địa điểm giữa, thì tìm kiếm trong mảng con bên trái
Bước 7 : Lặp lại cho tới khi tìm ra so khớp

Code mẫu cho giải thuật Tìm kiếm nội suy

? → Mảng
ɳ → Kích thước của ?
Ҳ → Giá trị cần tìm

hàm tìm kiếm nội suy Interpolation_Search()

   Gán Lo  →  0
   Gán Mid → -1
   Gán Hi  →  ɳ-1

   While Ҳ không so khớp
   
      if Lo bằng Hi OR ?[Lo] bằng ?[Hi]
         EXIT: Thất bại, không tìm ra Ҳ
      chấm dứt if
      
      Gán Mid = Lo + ((Hi - Lo) / (?[Hi] - ?[Lo])) * (Ҳ - ?[Lo]) 

      if ?[Mid] = Ҳ
         EXIT: Thành công, tìm ra tại Mid
      else 
         if ?[Mid] < Ҳ
            Seting Lo thành Mid+1
         else if ?[Mid] > Ҳ
            Seting Hi thành Mid-1
         chấm dứt if
      chấm dứt if
 
   Chấm dứt While

Chấm dứt hàm

Xem Thêm  Cách xóa dạng xem trong SQL Server - cách xóa chế độ xem trong sql

Chương trình minh họa tìm kiếm nội suy trong ₵

#includevàlt;stdio.hvàgt;

#define MAX 10

// khai bao mot đưa 
int menu[MAX] = { 10, 14, 19, 26, 27, 31, 33, 35, 42, 44 };

int find(int data) {
   int lo = 0;
   int hi = MAX - 1;
   int mid = -1;
   int comparisons = 1;      
   int index = -1;

   while(lo <= hi) {
      printf("nSo sanh lan thu %d  n" , comparisons ) ;
      printf("lo : %d, list[%d] = %dn", lo, lo, menu[lo]);
      printf("hi : %d, list[%d] = %dn", hi, hi, menu[hi]);
      
      comparisons++;

      // phan tu chot (probe) tai vi tri trung vi
      mid = lo + (((double)(hi - lo) / (menu[hi] - menu[lo])) * (data - menu[lo]));
      printf("Vi tri trung vi = %dn",mid);

      // tim thay du lieu
      if(menu[mid] == data) {
         index = mid;
         break;
      }else {
         if(menu[mid] < data) {
            // neu du lieu co gia tri lon hon, tim du lieu trong phan lon hon 
            lo = mid + 1;
         }else {
            // neu du lieu co gia tri nho hon, tim du lieu trong phan nho hon 
            hi = mid - 1;
         }
      }               
   }
   
   printf("nTong so phep so sanh da thuc hien: %d", --comparisons);
   return index;
}

int main() {
   //Tim vi tri cua phan tu 33
   int location = find(33);

   // Neu tim thay phan tu 
   if(location != -1)
      printf("nTim thay phan tu tai vi tri: %d" ,(location+1));
   else
      printf("Khong tim thay phan tu.");
   
   return 0;
}

Kết quả

Biên dịch và chạy chương trình ₵ trên sẽ cho kết quả:

Tìm kiếm nội suy trong C

 

Viết một bình luận