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ị được yêu cầu. Để thuật toán này hoạt động bình thường, 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ó lợi thế rất lớn về độ phức tạp về 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 có thể biết trước vị trí của dữ liệu đích. Ví dụ, trong trường hợp danh bạ điện thoại, nếu chúng ta 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ể chuyển trực tiếp đến 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 dữ liệu mong muốn không được tìm thấy 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.
Thăm dò vị trí trong tìm kiếm nội suy
Tìm kiếm nội suy tìm một mục cụ thể bằng cách tính toán vị trí đầu dò. Ban đầu, vị trí đầu dò là vị trí của phần lớn nhất ở giữa của bộ sưu tập.
Nếu khớp xảy ra, thì chỉ mục của mục sẽ đượ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 con bên phải của mục giữa. Nếu không, mục sẽ được tìm kiếm trong mảng con bên trái mục giữa. Quá trình này cũng tiếp tục trên mảng con cho đến khi kích thước của mảng con giảm xuống 0.
Độ 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 những tình huống thuận lợi.
Thuật toán
Vì đây là sự ứng biến 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ỉ mục giá trị dữ liệu '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
Để biết về cách thực hiện tìm kiếm nội suy trong ngôn ngữ lập trình C, hãy nhấp vào đây .