Bài 19 - Tìm kiếm nội suy trong cấu trúc dữ liệu & giải thuật

Tìm kiếm nội suy

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 tôi muốn tìm kiếm số điện thoại của Morphius. Ở đây, tìm kiếm tuyến tính và thậm chí tìm kiếm nhị phân sẽ có vẻ chậm vì chúng ta có thể trực tiếp nhảy vào không gian bộ nhớ nơi các tên bắt đầu từ 'M' được lưu trữ.

Định vị trong Tìm kiếm nhị phân

Trong tìm kiếm nhị phân, nếu không tìm thấy dữ liệu mong muốn thì phần còn lại của danh sách được chia thành hai phần, thấp hơn và cao hơn. Việc tìm kiếm được thực hiện ở một trong hai.

Ngay cả khi dữ liệu được sắp xếp, tìm kiếm nhị phân không tận dụng để thăm dò vị trí của dữ liệu mong muốn.

Tìm kiếm vị trí trong tìm kiếm nội suy

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])

where −

   A    = list

   Lo   = Lowest index of the list

   Hi   = Highest index of the list

   A[n] = Value stored at index n in the list

Nếu mục ở giữa lớn hơn mục, thì vị trí thăm dò lại được tính trong mảng phụ ở bên phải của mục giữa. Mặt khác, mục này được tìm kiếm trong phân đoạn bên trái của mục giữa. Quá trình này tiếp tục trên mảng con cho đến khi kích thước của phân đoạn giảm xuống bằng không.

Độ phức tạp thời gian chạy của thuật toán tìm kiếm nội suy là Ο (log (log n)) so với Ο (log n) của BST trong các tình huống thuận lợi.

Thuật toán

Vì đây là một ứng dụng của thuật toán BST hiện có, chúng tôi đang đề cập đến các bước để tìm kiếm chỉ số giá trị dữ liệu của 'mục tiêu', sử dụng thăm dò vị trí -

Step 1 − Start searching data from middle of the list.

Step 2 − If it is a match, return the index of the item, and exit.

Step 3 − If it is not a match, probe position.

Step 4 − Divide the list using probing formula and find the new midle.

Step 5 − If data is greater than middle, search in higher sub-list.

Step 6 − If data is smaller than middle, search in lower sub-list.

Step 7 − Repeat until match.

Mã giả

A → Array list

N → Size of A

X → Target Value

Procedure Interpolation_Search()

   Set Lo  →  0

   Set Mid → -1

   Set Hi  →  N-1

   While X does not match

      if Lo equals to Hi OR A[Lo] equals to A[Hi]

         EXIT: Failure, Target not found

      end if     

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

      if A[Mid] = X

         EXIT: Success, Target found at Mid

      else

         if A[Mid] < X

            Set Lo to Mid+1

         else if A[Mid] > X

            Set Hi to Mid-1

         end if

      end if

   End While

End Procedure

- Hiếu Kiều -