Ch&agrave;o mừng c&aacute;c bạn đến với kh&oacute;a học "Cấu tr&uacute;c dữ liệu v&agrave; Giải thuật" tại TEK4.VN!
Bạn đ&atilde; bao giờ tự hỏi rằng để trở th&agrave;nh một lập tr&igrave;nh vi&ecirc;n xuất sắc, bạn cần những kiến thức v&agrave; kỹ năng g&igrave;? Kh&oacute;a học n&agrave;y ch&iacute;nh l&agrave; ch&igrave;a kh&oacute;a để mở ra c&aacute;nh cửa của tri thức đ&oacute;. Với nội dung phong ph&uacute; v&agrave; chi tiết, kh&oacute;a học Cấu tr&uacute;c dữ liệu v&agrave; Giải thuật tại TEK4.VN hứa hẹn sẽ gi&uacute;p bạn x&acirc;y dựng nền tảng vững chắc v&agrave; th&agrave;nh thạo trong lập tr&igrave;nh.
Trong kh&oacute;a học n&agrave;y, ch&uacute;ng ta sẽ tập trung v&agrave;o việc kh&aacute;m ph&aacute; v&agrave; hiểu r&otilde; c&aacute;c cấu tr&uacute;c dữ liệu quan trọng như mảng, chuỗi k&yacute; tự, danh s&aacute;ch li&ecirc;n kết, ngăn xếp, h&agrave;ng đợi, bảng băm, tập hợp, c&acirc;y, đồ thị v&agrave; heap. C&aacute;c cấu tr&uacute;c dữ liệu n&agrave;y l&agrave; nền tảng của lập tr&igrave;nh, gi&uacute;p ch&uacute;ng ta giải quyết c&aacute;c vấn đề phức tạp một c&aacute;ch hiệu quả.
Kh&oacute;a học cũng sẽ gi&uacute;p bạn hiểu r&otilde; c&aacute;c thuật to&aacute;n cơ bản v&agrave; n&acirc;ng cao, bao gồm thuật to&aacute;n sắp xếp, thuật to&aacute;n t&igrave;m kiếm, thuật to&aacute;n t&igrave;m kiếm nhị ph&acirc;n, thuật to&aacute;n t&igrave;m kiếm chuỗi k&yacute; tự, giải thuật tham lam, thuật to&aacute;n quay lui v&agrave; quy hoạch động. Bạn sẽ học c&aacute;ch &aacute;p dụng c&aacute;c thuật to&aacute;n n&agrave;y v&agrave;o c&aacute;c vấn đề thực tế, gi&uacute;p tăng cường kỹ năng giải quyết vấn đề của m&igrave;nh.
Ngo&agrave;i ra, ch&uacute;ng m&igrave;nh sẽ chia sẻ một số kinh nghiệm cần thiết cho buổi phỏng vấn, gi&uacute;p bạn chuẩn bị tốt nhất cho c&aacute;c cơ hội nghề nghiệp li&ecirc;n quan đến lập tr&igrave;nh trong tương lai. Bạn sẽ được học c&aacute;ch hiểu r&otilde; y&ecirc;u cầu của người phỏng vấn, thể hiện kỹ năng lập tr&igrave;nh của m&igrave;nh một c&aacute;ch hiệu quả v&agrave; trả lời c&aacute;c c&acirc;u hỏi một c&aacute;ch tr&ocirc;i chảy. Ch&uacute;ng m&igrave;nh tự tin rằng, sau khi bạn ho&agrave;n th&agrave;nh kh&oacute;a học n&agrave;y, bạn sẽ trở n&ecirc;n nhạy b&eacute;n trong tư duy lập tr&igrave;nh hiệu quả.
H&atilde;y tham gia kh&oacute;a học n&agrave;y để t&igrave;m hiểu s&acirc;u hơn về lập tr&igrave;nh v&agrave; mở rộng kỹ năng của bạn. TEK4.VN rất mong được hỗ trợ bạn trong qu&aacute; tr&igrave;nh học tập n&agrave;y.

Cấu trúc dữ liệu và Giải thuật

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.
<h2 id="ftoc-heading-1" class="ftwp-heading" style="text-align: justify;">1. Kh&aacute;i niệm</h2>
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.
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, 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ử.
<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>
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.
<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>
C&aacute;c bước chung cho cả hai phương ph&aacute;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>
<img style="width: 50%; display: block; margin-left: auto; margin-right: auto;" src="https://tek4.vn/public_files/dca2293a-ae06-48d9-8d92-3db6202ee49f" alt="thuat-toan-tim-kiem-nhi-phan" />
<ul>
<li style="list-style-type: none;">
<ul>
<li>Gọi <code>x = 6</code> l&agrave; phần tử cần t&igrave;m.</li>
</ul>
</li>
<li>Bước 2: Đặt hai con trỏ <code>low</code> v&agrave; <code>high</code> lần lượt ở c&aacute;c vị tr&iacute; thấp nhất v&agrave; cao nhất</li>
</ul>
<img style="width: 50%; display: block; margin-left: auto; margin-right: auto;" src="https://tek4.vn/public_files/acbde0a5-1866-4cc6-9485-d3b2cf4df3b0" alt="thuat-toan-tim-kiem-nhi-phan-2" />
<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"><code>(arr[(high&nbsp;+&nbsp;low)/2])&nbsp;=&nbsp;8</code></li>
</ul>
<img style="width: 50%; display: block; margin-left: auto; margin-right: auto;" src="https://tek4.vn/public_files/bfe62dcc-e82f-4ff7-a8a4-c83a0ba49e07" alt="thuat-toan-tim-kiem-nhi-phan-3" />
<ul>
<li style="text-align: justify;">Bước 4: Nếu <code>x == mid</code> th&igrave; trả về <code>mid</code>. Nếu kh&ocirc;ng th&igrave;, so s&aacute;nh phần tử cần t&igrave;m với <code>m</code>.</li>
<li style="text-align: justify;">Bước 5: Nếu <code>x &gt; mid</code>, ta sẽ so s&aacute;nh <code>x</code> 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ử <code>mid</code>. Điều n&agrave;y được thực hiện bằng c&aacute;ch đặt <code>low = mid + 1</code>.</li>
<li style="text-align: justify;">Bước 6: Mặt kh&aacute;c, so s&aacute;nh <code>x</code> 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ử <code>mid</code>. Đ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"><code>high&nbsp;=&nbsp;mid&nbsp;-&nbsp;1</code>.</li>
</ul>
<img style="width: 50%; display: block; margin-left: auto; margin-right: auto;" src="https://tek4.vn/public_files/156db153-6e49-40ba-8910-241f81fd297d" alt="thuat-toan-tim-kiem-nhi-phan-4" />
<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"><code>low&nbsp;=&nbsp;high</code>.</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; <code>6</code>.</li>
</ul>
<img style="width: 50%; display: block; margin-left: auto; margin-right: auto;" src="https://tek4.vn/public_files/be55b087-46f4-4689-a6a7-cf0bd5d91748" alt="thuat-toan-tim-kiem-nhi-phan-5" />
Thuật to&aacute;n của t&igrave;m kiếm nhị ph&acirc;n như sau:
1. Phương ph&aacute;p sử dụng v&ograve;ng lặ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>
2. Phương thức sử dụng kỹ thuật đệ quy
<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>
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.
<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>
Kết quả:
<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(\log n)$</li>
<li>Độ phức tạp trong trường hợp xấu nhất: $O(\log n)$</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>
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;!