<p>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!</p>
<p>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.</p>
<p>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ả.</p>
<p>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.</p>
<p>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ả.</p>
<p>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.</p>

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

<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 tuyến t&iacute;nh. Ngo&agrave;i ra, ta sẽ triển khai v&iacute; dụ về kiểu thuật to&aacute;n n&agrave;y được viết 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 tuyến t&iacute;nh hay Linear Search l&agrave; thuật to&aacute;n t&igrave;m kiếm đơn giản nhất để t&igrave;m kiếm một phần tử trong danh s&aacute;ch theo thứ tự tuần tự. Ch&uacute;ng ta sẽ bắt đầu từ một đầu v&agrave; kiểm tra mọi phần tử cho đến khi phần tử cần t&igrave;m kh&ocirc;ng được t&igrave;m thấy.</p>
<h2 id="ftoc-heading-2" class="ftwp-heading" style="text-align: justify;">2. C&aacute;ch thức hoạt động của thuật to&aacute;n Linear Search</h2>
<p style="text-align: justify;">Bắt đầu từ phần tử ngo&agrave;i c&ugrave;ng b&ecirc;n tr&aacute;i của mảng v&agrave; lần lượt so s&aacute;nh phần tử ch&uacute;ng ta đang t&igrave;m kiếm với từng phần tử của mảng.</p>
<p style="text-align: justify;">Nếu c&oacute; sự tr&ugrave;ng khớp giữa phần tử ch&uacute;ng ta đang t&igrave;m kiếm v&agrave; một phần tử của mảng, ta sẽ trả về chỉ số của phần tử đ&oacute;.</p>
<p style="text-align: justify;">Nếu kh&ocirc;ng c&oacute; kết quả ph&ugrave; hợp n&agrave;o giữa phần tử ch&uacute;ng ta đang t&igrave;m kiếm v&agrave; một phần tử của mảng, trả về gi&aacute; trị l&agrave;&nbsp;<span id="urvanov-syntax-highlighter-6107cecb3edcd007670998" 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"><code><span class="crayon-o">-</span><span class="crayon-cn">1</span></code></span></span>&nbsp;hoặc bất kỳ gi&aacute; trị n&agrave;o m&agrave; kh&ocirc;ng nằm trong chỉ số của danh s&aacute;ch.</p>
<p style="text-align: justify;">V&iacute; dụ, c&aacute;c bước sau được thực hiện để t&igrave;m kiếm phần tử <code>k = 2</code> trong danh s&aacute;ch dưới đ&acirc;y.</p>
<ul>
<li style="text-align: justify;">Giả sử ta c&oacute; mảng như sau:</li>
</ul>
<p><img style="width: 50%; display: block; margin-left: auto; margin-right: auto;" src="https://tek4.vn/public_files/650bbeea-7c7a-4265-a1ba-4b9b8576e0d9" alt="thuat-toan-tim-kiem-tuyen-tinh" /></p>
<ul>
<li>Bắt đầu từ phần tử đầu ti&ecirc;n, so s&aacute;nh <code>k</code> với mỗi phần tử <code>x</code>.</li>
</ul>
<p><img style="width: 50%; display: block; margin-left: auto; margin-right: auto;" src="https://tek4.vn/public_files/081cef4b-ab71-4a6e-bfcc-08afeb388980" alt="thuat-toan-tim-kiem-tuyen-tinh-2" /></p>
<ul>
<li>Nếu <code>x == k</code>, ta sẽ trả về chỉ số của phần tử đ&oacute;.</li>
</ul>
<p><img style="width: 50%; display: block; margin-left: auto; margin-right: auto;" src="https://tek4.vn/public_files/d6f06af1-3433-432a-9cda-5d16a46731c6" alt="thuat-toan-tim-kiem-tuyen-tinh-3" /></p>
<ul>
<li>Nếu kh&ocirc;ng, trả về th&ocirc;ng b&aacute;o l&agrave; kh&ocirc;ng t&igrave;m thấy phần tử trong danh s&aacute;ch. Trong mảng tr&ecirc;n, gi&aacute; trị <code>k</code> cần t&igrave;m c&oacute; chỉ số l&agrave; 4 trong mảng.</li>
</ul>
<p>Thuật to&aacute;n cho Linear Search được m&ocirc; tả&nbsp;như sau:</p>
<pre class="language-cpp"><code>H&agrave;m t&igrave;m kiếm tuyến t&iacute;nh
  Sử dụng v&ograve;ng lặp for để duyệt qua từng phần tử trong danh s&aacute;ch/ tập hợp
    Nếu gi&aacute; trị của phần tử bằng gi&aacute; trị cần t&igrave;m
      Trả về chỉ số của phần tử đ&oacute; trong danh s&aacute;ch/ tập hợp</code></pre>
<p>V&iacute; dụ: Triển khai thuật to&aacute;n t&igrave;m kiếm phần tử trong mảng bằng ng&ocirc;n ngữ lập tr&igrave;nh C.</p>
<pre class="language-cpp"><code>#include &lt;stdio.h&gt;

int linear_search(int arr[], int n, int find) {
  for (int i = 0; i &lt; n; i++)
    if (arr[i] == find)
      return i;
  return -1;
}

int main() {
  int arr[] = {4, 6, 8, 11, 2, 7};
  int x = 2;
  int n = sizeof(arr) / sizeof(arr[0]);
  int kq = linear_search(arr, n, x);
  (kq == -1) ? printf("Kh&ocirc;ng t&igrave;m thấy") : printf("Gi&aacute; trị cần t&igrave;m nằm tại vị tr&iacute;: %d", kq);
}</code></pre>
<p>Kết quả:</p>
<pre class="language-cpp"><code>Gi&aacute; trị cần t&igrave;m nằm tại vị tr&iacute;: 4</code></pre>
<h2 id="ftoc-heading-3" class="ftwp-heading">3. Độ phức tạp của thuật to&aacute;n</h2>
<ul>
<li>Độ phức tạp về thời gian: $O(n)$</li>
<li>Độ phức tạp kh&ocirc;ng gian: $O(1)$</li>
</ul>
<h2 id="ftoc-heading-4" class="ftwp-heading">4. Ứng dụng của thuật to&aacute;n</h2>
<p>Được sử dụng cho c&aacute;c thao t&aacute;c t&igrave;m kiếm trong c&aacute;c mảng c&oacute; k&iacute;ch thước nhỏ hơn (&lt; 100 phần tử).</p>
<h2 id="ftoc-heading-5" class="ftwp-heading" style="text-align: left;">5. So s&aacute;nh giữa t&igrave;m kiếm nhị ph&acirc;n v&agrave; t&igrave;m kiếm tuyến t&iacute;nh</h2>
<table style="border-collapse: collapse; width: 41.3693%; height: 143px;" border="1">
<tbody>
<tr>
<td style="width: 48.0994%; text-align: center;">T&igrave;m kiếm nhị ph&acirc;n</td>
<td style="width: 51.8277%; text-align: center;">T&igrave;m kiếm tuyến t&iacute;nh</td>
</tr>
<tr>
<td style="width: 48.0994%; text-align: justify;">Y&ecirc;u cầu dữ liệu đầu v&agrave;o phải được sắp xếp.</td>
<td style="width: 51.8277%; text-align: justify;">Kh&ocirc;ng bắt buộc y&ecirc;u cầu điều kiện phải sắp xếp.</td>
</tr>
<tr>
<td style="width: 48.0994%; text-align: justify;">Y&ecirc;u cầu so s&aacute;nh theo thứ tự.</td>
<td style="width: 51.8277%; text-align: justify;">Chỉ y&ecirc;u cầu so s&aacute;nh ngang h&agrave;ng.</td>
</tr>
<tr>
<td style="width: 48.0994%; text-align: justify;">C&oacute; độ phức tạp của thuật to&aacute;n l&agrave; $O(\log n)$.</td>
<td style="width: 51.8277%; text-align: justify;">C&oacute; độ phức tạp của thuật to&aacute;n l&agrave; $O(n)$.</td>
</tr>
<tr>
<td style="width: 48.0994%; text-align: justify;">Y&ecirc;u cầu quyền truy cập ngẫu nhi&ecirc;n v&agrave;o dữ liệu.</td>
<td style="width: 51.8277%; text-align: justify;">Chỉ y&ecirc;u cầu quyền truy cập theo tuần tự (điều n&agrave;y c&oacute; thể rất quan trọng, điều đ&oacute; c&oacute; nghĩa l&agrave; t&igrave;m kiếm tuyến t&iacute;nh c&oacute; thể truyền dữ liệu c&oacute; k&iacute;ch thước t&ugrave;y &yacute;).</td>
</tr>
</tbody>
</table>
<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 tuyến t&iacute;nh hay Linear Search. 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>

Thuật toán tìm kiếm tuyến tính