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

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 tiến 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 chính xác thì tập dữ liệu phải được sắp xếp.

Binary Search có lợi thế lớn về độ phức tạp thời gian khi so sánh với Linear Search. Linear Search có độ phức tạp trường hợp xấu nhất là Ο(n) trong khi Binary Search là Ο(log n).

Có một số tình huống mà vị trí của dữ liệu cần tìm có thể đã được biết trước. Ví dụ, trong trường hợp danh bạ điện thoại, nếu chúng ta muốn tìm số điện thoại của Hương chẳng hạn. 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à chúng ta có thể trực tiếp nhảy tới phần không gian bộ nhớ có tên bắt đầu với H được lưu giữ.

Xác định vị trí trong Binary Search

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

Dò vị trí 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ử cụ thể bằng việc tính toán vị trí dò (Probe Position). Ban đầu thì vị trí dò là vị trí của phần tử nằm ở giữa nhất của tập dữ liệu.

Nếu tìm thấy kết nối thì chỉ mục của phần tử được trả về. Để chia danh sách thành hai phần, chúng ta sử dụng phương thức sau:

mid = Lo + ((Hi - Lo) / (A[Hi] - A[Lo])) * (X - A[Lo])

Trong đó:
   A    = danh sách
   Lo   = ch mc thp nht ca danh sách
   Hi   = ch mc cao nht ca danh sách
   A[n] = giá tr được lưu gi ti ch mc n trong danh sách

Nếu phần tử cần tìm có giá trị lớn 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à chúng ta lại tiếp tục tính vị trí dò; nếu không phần tử cần tìm sẽ ở mảng con bên trái phần tử ở giữa. Tiến trình này tiến tụp diễn ra trên các mảng con cho tới khi kích cỡ của mảng con giảm về 0.

Độ phức tạp thời gian chạy của Interpolation Search là Ο(log (log n)), trong khi của Binary Search là Ο(log n).

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

Bởi vì đây là sự cải tiến của giải thuật Binary Search nên 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 vị trí dò.

Bước 1 : Bt đầu tìm kiếm d liu t phn gia ca danh sách
Bước 2 : Nếu đây là mt so khp (mt kết ni), thì tr v ch mc ca phn tử, và thoát.
Bước 3 : Nếu không phi là mt so khp, thì là v trí dò.
Bước 4 : Chia danh sách bi s dng phép tính tìm v trí dò và tìm v trí gia mi.
Bước 5 : Nếu d liu cn tìm ln hơn giá tr ti v trí gia, thì tìm kiếm trong mng con bên phi.
Bước 6 : Nếu d liu cn tìm nh hơn giá tr ti v trí gia, thì tìm kiếm trong mng con bên trái
Bước 7 : Lp li cho ti khi tìm thy so khp

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

A  Mng
N  Kích c ca A
X  Giá tr cn tìm

hàm tìm kiếm ni suy Interpolation_Search()

   Gán Lo    0
   Gán Mid  -1
   Gán Hi    N-1

   While X không so khp
   
      if Lo bng Hi OR A[Lo] bng A[Hi]
         EXIT: Tht bi, không tìm thy X
      kết thúc if
      
      Gán Mid = Lo + ((Hi - Lo) / (A[Hi] - A[Lo])) * (X - A[Lo]) 

      if A[Mid] = X
         EXIT: Thành công, tìm thy ti Mid
      else 
         if A[Mid] < X
            Thiết lp Lo thành Mid+1
         else if A[Mid] > X
            Thiết lp Hi thành Mid-1
    kết thúc if
      kết thúc if
 
   Kết thúc While

Kết thúc hàm