Thuật toán tìm kiếm nội suy

<p style="text-align: justify;">Trong b&agrave;i viết n&agrave;y, ta sẽ c&ugrave;ng t&igrave;m hiểu về thuật to&aacute;n t&igrave;m kiếm nội suy hay Interpolation Search. Ngo&agrave;i ra, ta sẽ triển khai v&iacute; dụ về kiểu thuật to&aacute;n n&agrave;y bằng ng&ocirc;n ngữ lập tr&igrave;nh C.</p> <h2 id="ftoc-heading-1" class="ftwp-heading" style="text-align: justify;">1. Kh&aacute;i niệm</h2> <p style="text-align: justify;">T&igrave;m kiếm nội suy hay Interpolation Search l&agrave; một loại thuật to&aacute;n hay giải thuật t&igrave;m kiếm. T&igrave;m kiếm nội suy l&agrave; một thuật to&aacute;n cải tiến hơn so với t&igrave;m kiếm nhị ph&acirc;n cho c&aacute;c trường hợp, trong đ&oacute; c&aacute;c gi&aacute; trị trong một mảng đ&atilde; được sắp xếp được ph&acirc;n phối đồng đều.</p> <p style="text-align: justify;">T&igrave;m kiếm nhị ph&acirc;n sẽ chuyển đến phần tử giữa để kiểm tra, v&agrave; loại bỏ c&aacute;c phần tử c&ograve;n lại t&ugrave;y thuộc v&agrave;o gi&aacute; trị t&igrave;m kiếm v&agrave; gi&aacute; trị của phần tử nằm ở giữa. Mặt kh&aacute;c, giải thuật t&igrave;m kiếm nội suy c&oacute; thể đi đến c&aacute;c vị tr&iacute; kh&aacute;c nhau t&ugrave;y theo gi&aacute; trị của kh&oacute;a đang được t&igrave;m kiếm. Tại mỗi bước t&igrave;m kiếm, t&igrave;m kiếm nội suy sẽ t&iacute;nh to&aacute;n v&ugrave;ng kh&ocirc;ng gian m&agrave; phần tử cần t&igrave;m c&oacute; thể xuất hiện, dựa tr&ecirc;n gi&aacute; trị Low v&agrave; High của kh&ocirc;ng gian t&igrave;m kiếm.</p> <p style="text-align: justify;">V&iacute; dụ, nếu gi&aacute; trị của kh&oacute;a gần với phần tử cuối c&ugrave;ng, t&igrave;m kiếm nội suy c&oacute; khả năng sẽ c&oacute; xu hướng bắt đầu qu&aacute; tr&igrave;nh t&igrave;m kiếm ở ph&iacute;a cuối.</p> <p style="text-align: justify;">T&igrave;m kiếm nội suy sử dụng c&ocirc;ng thức sau đ&acirc;y để t&igrave;m kiếm vị tr&iacute; ở giữa, trong đ&oacute; arr[low] v&agrave; arr[high] l&agrave; v&ugrave;ng kh&ocirc;ng gian t&igrave;m kiếm v&agrave; x l&agrave; phần tử cần t&igrave;m.</p> <pre class="language-cpp"><code>Mid = low + ((x-arr[low])*(high-low)/(arr[high] &ndash; arr[low]));</code></pre> <p style="text-align: justify;">C&aacute;c bước về c&aacute;ch hoạt động của giải thuật t&igrave;m kiếm nội suy:</p> <ul style="text-align: justify;"> <li>Trong một v&ograve;ng lặp, ta sẽ t&iacute;nh gi&aacute; trị của Mid bằng c&ocirc;ng thức b&ecirc;n tr&ecirc;n.</li> <li>Nếu c&oacute; sự tr&ugrave;ng khớp, ta trả về chỉ số của phần tử v&agrave; kết th&uacute;c việc t&igrave;m kiếm.</li> <li>Nếu phần tử nhỏ hơn arr[mid], ta sẽ t&iacute;nh to&aacute;n vị tr&iacute; thăm d&ograve; của mảng con b&ecirc;n tr&aacute;i. Nếu kh&ocirc;ng, ta sẽ thực hiện qu&aacute; tr&igrave;nh t&iacute;nh to&aacute;n tương tự trong mảng con b&ecirc;n phải.</li> <li>Lặp lại cho đến khi t&igrave;m thấy kết quả ph&ugrave; hợp hoặc mảng con giảm xuống 0.</li> </ul> <h2 id="ftoc-heading-2" class="ftwp-heading" style="text-align: justify;">2. V&iacute; dụ về t&igrave;m kiếm nội suy</h2> <p style="text-align: justify;">Sau đ&acirc;y l&agrave; một v&iacute; dụ về c&aacute;ch viết cho giải thuật t&igrave;m kiếm nội suy dựa tr&ecirc;n c&aacute;c bước ta đ&atilde; cung cấp.</p> <p style="text-align: justify;">V&iacute; dụ: Triển khai t&igrave;m kiếm nội suy bằng ng&ocirc;n ngữ lập tr&igrave;nh C.</p> <pre class="language-cpp"><code>#include &lt;stdio.h&gt; int search(int arr[], int n, int find) { int low = 0, high = n - 1, mid; while (arr[high] != arr[low] &amp;&amp; find &gt;= arr[low] &amp;&amp; find &lt;= arr[high]) { mid = low + ((find - arr[low]) * (high - low) / (arr[high] - arr[low])); if (find == arr[mid]) { return mid; } else if (find &lt; arr[mid]) { high = mid - 1; } else { low = mid + 1; } } if (find == arr[low]) { return low; } else { return -1; } } int main(void) { int arr[] = {4, 6, 8, 11, 13, 15}; int value_to_find = 6; int n = sizeof(arr)/sizeof(arr[0]); int pos = search(arr, n, value_to_find); if (pos != -1) { printf("Phần tử cần t&igrave;m nằm ở vị tr&iacute; %d", pos); } else { printf("Kh&ocirc;ng t&igrave;m thấy"); } return 0; }</code></pre> <p>Kết quả:</p> <pre class="language-cpp"><code>Phần tử cần t&igrave;m nằm ở vị tr&iacute; 1</code></pre> <h2 id="ftoc-heading-3" class="ftwp-heading">3. Độ phức tạp của thuật to&aacute;n</h2> <p style="text-align: justify;">Nếu c&aacute;c phần tử được ph&acirc;n bố đồng đều th&igrave; độ phức tạp về thời gian l&agrave; $O(loglogn)$. Trong trường hợp xấu nhất, n&oacute; c&oacute; thể l&agrave; $O(n)$. V&igrave; vậy, để t&igrave;m kiếm hoạt động hiệu quả, c&aacute;c phần tử hay dữ liệu trong mảng phải được sắp xếp v&agrave; ph&acirc;n phối đồng đều.</p> <p style="text-align: justify;">N&oacute;i chung, t&igrave;m kiếm nội suy l&agrave; một kh&aacute;i niệm quan trọng cần hiểu khi n&oacute;i đến thuật to&aacute;n. Ngo&agrave;i ra, điều quan trọng l&agrave; phải so s&aacute;nh n&oacute; với c&aacute;c thuật to&aacute;n kh&aacute;c như t&igrave;m kiếm nhị ph&acirc;n. C&aacute;c bạn c&oacute; thể xem lại thuật to&aacute;n t&igrave;m kiếm nhị ph&acirc;n để biết chi tiết hơn.</p> <p style="text-align: justify;">Như vậy, thuật to&aacute;n x&aacute;c định phần tử nội suy v&agrave; thuật to&aacute;n x&aacute;c định phần tử nhị ph&acirc;n l&agrave; gần giống nhau. Tuy nhi&ecirc;n, thuật to&aacute;n nội suy sẽ sử dụng một c&ocirc;ng thức để t&iacute;nh cho phần tử ở giữa, c&ograve;n thuật to&aacute;n t&igrave;m kiếm nhị ph&acirc;n đơn giản sẽ x&aacute;c định phần tử nằm giữa của mảng v&agrave; cứ như vậy cho tới khi x&aacute;c định được phần tử trong mảng.</p> <p style="text-align: justify;">Tr&ecirc;n đ&acirc;y l&agrave; kh&aacute;i niệm v&agrave; v&iacute; dụ cơ bản về thuật to&aacute;n t&igrave;m kiếm nội suy. Hy vọng mọi người c&oacute; thể &aacute;p dụng v&agrave;o trong chương tr&igrave;nh của m&igrave;nh. Nếu mọi người c&oacute; đ&oacute;ng g&oacute;p g&igrave; th&ecirc;m th&igrave; c&oacute; thể để c&aacute;c b&igrave;nh luận b&ecirc;n dưới b&agrave;i viết n&agrave;y. Mọi người h&atilde;y tiếp tục theo d&otilde;i c&aacute;c b&agrave;i tiếp theo v&agrave; cập nhật c&aacute;c b&agrave;i mới nhất tr&ecirc;n&nbsp;<a href="../../../">tek4</a>&nbsp;nh&eacute;!</p>