Cấu trúc dữ liệu - Tìm kiếm nội suy

Tìm kiếm nội suy là một biến thể cải tiến của tìm kiếm nhị phân. Thuật toán tìm kiếm này hoạt động trên vị trí thăm dò của giá trị yêu cầu. Để thuật toán này hoạt động chính xác, việc thu thập dữ liệu phải ở dạng được sắp xếp và phân bổ đều.

Tìm kiếm nhị phân có một lợi thế rất lớn về độ phức tạp thời gian so với tìm kiếm tuyến tính. Tìm kiếm tuyến tính có độ phức tạp trong trường hợp xấu nhất là Ο (n) trong khi tìm kiếm nhị phân có (log n).

Có những trường hợp vị trí của dữ liệu đích 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 thấy một mục cụ thể bằng cách tính toán vị trí thăm dò. Ban đầu, vị trí thăm dò là vị trí của hầu hết các mục giữa của bộ sưu tập.

Nếu một trận đấu xảy ra, thì chỉ mục của mục được trả về. Để chia danh sách thành hai phần, chúng tôi sử dụng phương pháp 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

Được cập nhật: 14 tháng 4 lúc 0:33:37 | Lượt xem: 619