Thuật toán tìm kiếm nhị phân

<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ề c&aacute;ch l&agrave;m việc của thuật to&aacute;n t&igrave;m kiếm nhị ph&acirc;n. Ngo&agrave;i ra, ta sẽ triển khai v&iacute; dụ về c&aacute;ch thức l&agrave;m việc của 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 nhị ph&acirc;n hay Binary Search l&agrave; một thuật to&aacute;n t&igrave;m kiếm để t&igrave;m ra vị tr&iacute; của một phần tử trong một mảng được sắp xếp. Trong c&aacute;ch tiếp cận n&agrave;y, phần tử lu&ocirc;n được t&igrave;m kiếm ở giữa một phần của mảng.</p> <p style="text-align: justify;">T&igrave;m kiếm nhị ph&acirc;n chỉ c&oacute; thể được thực hiện tr&ecirc;n một danh s&aacute;ch c&aacute;c phần tử đ&atilde; được sắp xếp. Nếu c&aacute;c phần tử chưa được sắp xếp, ch&uacute;ng ta cần sắp xếp ch&uacute;ng trước khi thực hiện qu&aacute; tr&igrave;nh t&igrave;m kiếm phần tử.</p> <h2 id="ftoc-heading-2" class="ftwp-heading" style="text-align: justify;">2. C&aacute;ch thức hoạt động của t&igrave;m kiếm nhị ph&acirc;n</h2> <p style="text-align: justify;">Thuật to&aacute;n t&igrave;m kiếm nhị ph&acirc;n c&oacute; thể được thực hiện theo hai c&aacute;ch được thảo luận dưới đ&acirc;y.</p> <ol style="text-align: justify;"> <li>Phương ph&aacute;p sử dụng v&ograve;ng lặp.</li> <li>Phương ph&aacute;p đệ quy.</li> </ol> <p style="text-align: justify;">C&aacute;c bước chung cho cả hai phương ph&aacute;p.</p> <ul> <li style="text-align: justify;">Bước 1: Giả sử ta c&oacute; mảng chứa phần tử cần t&igrave;m c&oacute; dạng như sau:</li> </ul> <p><img style="width: 100%;" src="../../../public_files/51e699b3-95c1-4932-9240-29f5ef3c6ed3" alt="thuat-toan-tim-kiem-nhi-phan" /></p> <ul> <li style="list-style-type: none;"> <ul> <li>Gọi x = 6 l&agrave; phần tử cần t&igrave;m.</li> </ul> </li> <li>Bước 2: Đặt hai con trỏ Low v&agrave; High lần lượt ở c&aacute;c vị tr&iacute; thấp nhất v&agrave; cao nhất</li> </ul> <p><img style="width: 100%;" src="../../../public_files/c36a024c-01c5-43c9-b0c0-88f531702e3d" alt="thuat-toan-tim-kiem-nhi-phan-2" /></p> <ul> <li>Bước 3: T&igrave;m phần tử giữa ở giữa của mảng tức l&agrave;&nbsp;<span id="urvanov-syntax-highlighter-6107d006a5dc4152452133" class="urvanov-syntax-highlighter-syntax urvanov-syntax-highlighter-syntax-inline crayon-theme-classic crayon-theme-classic-inline urvanov-syntax-highlighter-font-monaco"><span class="crayon-pre urvanov-syntax-highlighter-code"><span class="crayon-sy">(</span><span class="crayon-v">arr</span><span class="crayon-sy">[</span><span class="crayon-sy">(</span><span class="crayon-v">high</span><span class="crayon-h">&nbsp;</span><span class="crayon-o">+</span><span class="crayon-h">&nbsp;</span><span class="crayon-v">low</span><span class="crayon-sy">)</span><span class="crayon-o">/</span><span class="crayon-cn">2</span><span class="crayon-sy">]</span><span class="crayon-sy">)</span><span class="crayon-h">&nbsp;</span><span class="crayon-o">=</span><span class="crayon-h">&nbsp;</span><span class="crayon-cn">8</span></span></span></li> </ul> <p><span class="urvanov-syntax-highlighter-syntax urvanov-syntax-highlighter-syntax-inline crayon-theme-classic crayon-theme-classic-inline urvanov-syntax-highlighter-font-monaco"><img style="width: 100%;" src="../../../public_files/0d90c7fb-e07d-4451-a94f-f7625b4170e9" alt="thuat-toan-tim-kiem-nhi-phan-3" /></span></p> <ul> <li style="text-align: justify;">Bước 4: Nếu x == mid th&igrave; trả về mid. Nếu kh&ocirc;ng th&igrave;, so s&aacute;nh phần tử cần t&igrave;m với m.</li> <li style="text-align: justify;">Bước 5: Nếu x &gt; mid, ta sẽ so s&aacute;nh x với phần tử ở giữa của c&aacute;c phần tử ở ph&iacute;a b&ecirc;n phải của phần tử mid. Điều n&agrave;y được thực hiện bằng c&aacute;ch đặt&nbsp;<span id="urvanov-syntax-highlighter-6107d006a5dcd779070416" class="urvanov-syntax-highlighter-syntax urvanov-syntax-highlighter-syntax-inline crayon-theme-classic crayon-theme-classic-inline urvanov-syntax-highlighter-font-monaco"><span class="crayon-pre urvanov-syntax-highlighter-code"><span class="crayon-v">low</span><span class="crayon-h">&nbsp;</span><span class="crayon-o">=</span><span class="crayon-h">&nbsp;</span><span class="crayon-v">mid</span><span class="crayon-h">&nbsp;</span><span class="crayon-o">+</span><span class="crayon-h">&nbsp;</span><span class="crayon-cn">1</span></span></span>.</li> <li style="text-align: justify;">Bước 6: Mặt kh&aacute;c, so s&aacute;nh x với phần tử ở giữa của c&aacute;c phần tử ở b&ecirc;n tr&aacute;i của phần tử mid. Điều n&agrave;y được thực hiện bằng c&aacute;ch thiết lập&nbsp;<span id="urvanov-syntax-highlighter-6107d006a5dcf281523537" class="urvanov-syntax-highlighter-syntax urvanov-syntax-highlighter-syntax-inline crayon-theme-classic crayon-theme-classic-inline urvanov-syntax-highlighter-font-monaco"><span class="crayon-pre urvanov-syntax-highlighter-code"><span class="crayon-v">high</span><span class="crayon-h">&nbsp;</span><span class="crayon-o">=</span><span class="crayon-h">&nbsp;</span><span class="crayon-v">mid</span><span class="crayon-h">&nbsp;</span><span class="crayon-o">-</span><span class="crayon-h">&nbsp;</span><span class="crayon-cn">1</span></span></span>.</li> </ul> <p><img style="width: 100%;" src="../../../public_files/ab6810d8-fee3-429e-88e8-49e89c0f401e" alt="thuat-toan-tim-kiem-nhi-phan-4" /></p> <ul> <li>Bước 7: Lặp lại từ bước 3 đến bước 6 cho đến khi&nbsp;<span id="urvanov-syntax-highlighter-6107d006a5dd1364268332" class="urvanov-syntax-highlighter-syntax urvanov-syntax-highlighter-syntax-inline crayon-theme-classic crayon-theme-classic-inline urvanov-syntax-highlighter-font-monaco"><span class="crayon-pre urvanov-syntax-highlighter-code"><span class="crayon-v">low</span><span class="crayon-h">&nbsp;</span><span class="crayon-o">=</span><span class="crayon-h">&nbsp;</span><span class="crayon-v">high</span></span></span>.</li> <li>Bước 8: V&agrave; cuối c&ugrave;ng ta sẽ t&igrave;m được phần tử cần t&igrave;m l&agrave; 6.</li> </ul> <p><img style="width: 100%;" src="../../../public_files/55ef1e2c-8731-4f5d-8541-c46178cbe8bd" alt="thuat-toan-tim-kiem-nhi-phan-5" /></p> <p>Thuật to&aacute;n của t&igrave;m kiếm nhị ph&acirc;n như sau:</p> <p><em>1. Phương ph&aacute;p sử dụng v&ograve;ng lặp</em></p> <pre class="language-cpp"><code>Thực hiện cho đến khi c&aacute;c con trỏ low trỏ c&ugrave;ng vị tr&iacute; của con trỏ high. mid = (low + high) / 2 Nếu x == arr[mid] Trả về mid Nếu x &gt; arr[mid] // x ở ph&iacute;a b&ecirc;n phải low = mid + 1 Nếu kh&ocirc;ng // x ở b&ecirc;n tr&aacute;i high = mid &ndash; 1</code></pre> <p><em>2. Phương thức sử dụng kỹ thuật đệ quy</em></p> <pre class="language-cpp"><code>H&agrave;m t&igrave;m kiếm nhị ph&acirc;n(arr, x, low, high) Nếu low &gt; high Trả về False Nếu kh&ocirc;ng mid = (low + high) / 2 Nếu x = arr[mid] Trả về mid Nếu x &lt; arr[mid] Trả về h&agrave;m t&igrave;m kiếm nhị ph&acirc;n(arr, x, mid + 1, high) Nếu kh&ocirc;ng Trả về h&agrave;m t&igrave;m kiếm nhị ph&acirc;n (arr, x, low, mid - 1)</code></pre> <p>V&iacute; dụ: Triển khai t&igrave;m kiếm nhị ph&acirc;n 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 x, int low, int high) { while (low &lt;= high) { int mid = low + (high - low) / 2; if (arr[mid] == x) return mid; if (arr[mid] &lt; x) low = mid + 1; else high = mid - 1; } return -1; } int main(void) { int arr[] = {4, 6, 8, 11, 13, 15}; int n = sizeof(arr) / sizeof(arr[0]); int x = 6; int kq = search(arr, x, 0, n - 1); if (kq == -1) printf("Kh&ocirc;ng t&igrave;m thấy"); else printf("Phần tử cần t&igrave;m nằm ở vị tr&iacute; %d", kq); return 0; } Kết quả: Phần tử cần t&igrave;m nằm ở vị tr&iacute; 1 V&iacute; dụ 2: #include &lt;stdio.h&gt; int search(int arr[], int find, int low, int high) { if (high &gt;= low) { int mid = low + (high - low) / 2; if (arr[mid] == find) return mid; if (arr[mid] &gt; find) return search(arr, find, low, mid - 1); return search(arr, find, mid + 1, high); } return -1; } int main(void) { int arr[] = {4, 6, 8, 11, 13, 15}; int n = sizeof(arr) / sizeof(arr[0]); int find = 6; int kq = search(arr, find, 0, n - 1); if (kq == -1) printf("Kh&ocirc;ng t&igrave;m thấy"); else printf("Phần tử nằm tại vị tr&iacute; %d", kq); }</code></pre> <p>Kết quả:</p> <pre class="language-cpp"><code>Phần tử nằm tại vị tr&iacute; 1</code></pre> <h2 id="ftoc-heading-3" class="ftwp-heading" style="text-align: justify;">3. Độ phức tạp của thuật to&aacute;n</h2> <h3 style="text-align: justify;">3.1. Độ phức tạp về thời gian</h3> <ul style="text-align: justify;"> <li>Độ phức tạp trong trường hợp tốt nhất: $O(1)$</li> <li>Độ phức tạp trong trường hợp trung b&igrave;nh: $O(logn)$</li> <li>Độ phức tạp trong trường hợp xấu nhất: $O(logn)$</li> </ul> <h3 style="text-align: justify;">3.2. Độ phức tạp về kh&ocirc;ng gian</h3> <ul style="text-align: justify;"> <li>Độ phức tạp kh&ocirc;ng gian của t&igrave;m kiếm nhị ph&acirc;n l&agrave; $O(n)$.</li> </ul> <h2 id="ftoc-heading-4" class="ftwp-heading" style="text-align: justify;">4. Ứng dụng của thuật to&aacute;n</h2> <ul style="text-align: justify;"> <li>Sử dụng trong c&aacute;c thư viện Java, .Net, C ++ STL</li> <li>Trong khi gỡ lỗi, t&igrave;m kiếm nhị ph&acirc;n được sử dụng để x&aacute;c định vị tr&iacute; xảy ra lỗi.</li> </ul> <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 nhị ph&acirc;n. 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>