Cách Giải Tìm Kiếm Tuần Tự (Linear Search), Dể Hiểu

Thuật toán Tìm Kiếm Tuần Tự, xuất phát từ nhu cầu cơ bản trong lập trình, nơi con người cần tìm kiếm thông tin trong danh sách. Nó đơn giản, trực quan; mỗi phần tử được kiểm tra lần lượt. Trong thế giới dữ liệu phức tạp, Tìm Kiếm Tuần Tự vẫn giữ giá trị cốt lõi: sự đơn giản.

Định Nghĩa

Tìm Kiếm Tuần Tự (Linear Search) là một thuật toán dùng để tìm kiếm một phần tử trong một mảng. Mảng có thể chứa các giá trị bất kỳ và các phần tử trong mảng không nhất thiết phải được sắp xếp. Thuật toán này đi qua từng phần tử của mảng, so sánh mỗi phần tử với giá trị cần tìm, cho đến khi tìm thấy phần tử hoặc kiểm tra hết tất cả các phần tử trong mảng.

Quá trình tìm kiếm bắt đầu từ phần tử đầu tiên của mảng và tiếp tục tuần tự qua từng phần tử cho đến khi tìm thấy phần tử cần tìm. Nếu phần tử được tìm thấy, thuật toán trả về chỉ số (index) của phần tử trong mảng. Nếu không tìm thấy phần tử nào khớp, thuật toán trả về -1.

Tìm Kiếm Tuần Tự có thể áp dụng cho mảng một chiều hoặc mảng đa chiều, tuy nhiên trong trường hợp mảng đa chiều, thuật toán cần được điều chỉnh để duyệt qua các chiều khác nhau. Thực tế, nó không yêu cầu mảng phải được sắp xếp, làm cho thuật toán rất linh hoạt và dễ áp dụng.

Điểm mạnh của thuật toán này là sự đơn giản và tính trực quan, nhưng nhược điểm của nó là hiệu suất kém khi làm việc với các mảng lớn. Mặc dù vậy, trong các trường hợp mảng nhỏ hoặc khi không có điều kiện sắp xếp, Tìm Kiếm Tuần Tự vẫn là một lựa chọn hợp lý.

Cách Giải

Thuật toán Tìm Kiếm Tuần Tự hoạt động trên nguyên tắc duyệt qua từng phần tử trong mảng một cách tuần tự. Sau đây là cách giải chi tiết:

Bắt đầu từ phần tử đầu tiên trong mảng.
So sánh phần tử đó với giá trị bạn đang tìm kiếm.
Nếu phần tử trùng khớp, trả về chỉ số của nó.
Nếu không trùng, chuyển sang phần tử tiếp theo và lặp lại bước 2.
Nếu bạn đã duyệt hết mảng mà không tìm thấy giá trị, trả về -1.

Bạn thấy đó, thuật toán này đơn giản và dễ hiểu. Nó chỉ yêu cầu bạn đi qua từng phần tử một cách tuần tự, và mỗi lần so sánh là một quyết định. Cách tiếp cận này tuy đơn giản, nhưng nó không phải lúc nào cũng hiệu quả khi dữ liệu trở nên lớn và phức tạp hơn.

Để dể hình dung hơn, bạn có thể xem diễn họa của thuật toán tại đây: https://www.w3schools.com/dsa/dsa_algo_linearsearch.php

Triển Khai

Để triển khai thuật toán Tìm Kiếm Tuần Tự, chúng ta cần:

Một mảng chứa các giá trị cần tìm kiếm.
Một giá trị mục tiêu cần tìm trong mảng.
Một vòng lặp đi qua mảng từ đầu đến cuối.
Một câu lệnh if để so sánh giá trị hiện tại với giá trị mục tiêu, và trả về chỉ số hiện tại nếu tìm thấy giá trị mục tiêu.
Sau khi vòng lặp kết thúc, trả về -1, vì lúc này chúng ta biết rằng giá trị mục tiêu không có trong mảng.

Mã TypeScript sẽ trông như sau:

import { expect } from 'jsr:@std/expect';

function linearSearch(nums: number[], target: number): number {
  // Vòng lặp qua từng phần tử trong mảng từ đầu đến cuối
  for (let i = 0; i < nums.length; i++) {
    // Kiểm tra xem phần tử hiện tại có bằng với giá trị cần tìm không
    if (nums[i] === target) {
      // Nếu tìm thấy, trả về chỉ số hiện tại
      return i;
    }
  }

  // Nếu không tìm thấy giá trị trong mảng, trả về -1
  return -1;
}

Deno.test('found', () => {
  const input = [3, 15, 7, 1, 12, 19, 5, 8, 2, 10];

  expect(linearSearch(input, 1)).toStrictEqual(3);
});

Deno.test('not found', () => {
  const input = [3, 15, 7, 1, 12, 19, 5, 8, 2, 10];

  expect(linearSearch(input, 4)).toStrictEqual(-1);
});

Big O

Trong trường hợp tốt nhất, độ phức tạp thời gian của thuật toán là O(1). Điều này xảy ra khi phần tử bạn đang tìm kiếm là phần tử đầu tiên trong mảng. Khi đó, thuật toán chỉ cần một lần so sánh duy nhất để tìm ra kết quả.

Trong trường hợp xấu nhất, độ phức tạp thời gian của thuật toán là O(n). Điều này xảy ra khi phần tử bạn cần tìm là phần tử cuối cùng trong mảng hoặc không có trong mảng. Bạn sẽ phải kiểm tra tất cả các phần tử trước khi biết được kết quả.

Trong trường hợp trung bình, độ phức tạp thời gian của thuật toán là O(n/2), bởi vì bạn sẽ phải kiểm tra một nửa số phần tử trong mảng. Tuy nhiên, trong phân tích độ phức tạp Big O, chúng ta bỏ qua các hằng số và chỉ quan tâm đến yếu tố n, vì vậy độ phức tạp thời gian của thuật toán vẫn là O(n).

Độ phức tạp không gian của thuật toán là O(1), vì thuật toán chỉ sử dụng một lượng bộ nhớ cố định (biến i trong vòng lặp), không phụ thuộc vào kích thước của mảng.

Toàn Cảnh

Trong bức tranh lớn hơn của các thuật toán tìm kiếm, Tìm Kiếm Tuần Tự là nền tảng và thường là bước đầu tiên để hiểu các thuật toán tìm kiếm phức tạp hơn.

So với các thuật toán như Tìm Kiếm Nhị Phân yêu cầu mảng đã được sắp xếp trước, Tìm Kiếm Tuần Tự có lợi thế vì nó hoạt động trên bất kỳ tập dữ liệu nào, dù sắp xếp hay chưa.

Tìm Kiếm Tuần Tự là một lựa chọn phù hợp trong các hệ thống đơn giản hoặc những trường hợp mà số lượng phần tử ít.

Dù đơn giản nhưng nó tạo ra một nguyên tắc cơ bản trong tìm kiếm dữ liệu, giúp bạn hiểu và phát triển lên các thuật toán tìm kiếm tối ưu hơn.

Ứng Dụng

Bạn có thể dùng Tìm Kiếm Tuần Tự trong những tình huống cần kiểm tra một danh sách ngắn, như tìm một người cụ thể trong danh sách khách mời của một sự kiện.

Hoặc trong lập trình, khi bạn kiểm tra từng phần tử trong một mảng nhỏ để xác định xem nó có đáp ứng một điều kiện nào đó hay không.

Ngoài ra, thuật toán này cũng hữu ích khi bạn chỉ cần tìm kiếm một lần, và không nhất thiết phải tối ưu hóa tốc độ.

Nó cũng là một phương pháp hữu ích khi bạn làm việc với dữ liệu không sắp xếp, hoặc khi bạn không thể sắp xếp lại dữ liệu vì những lý do nhất định.

Hiểu Lầm

Một hiểu lầm thường gặp là nghĩ rằng Tìm Kiếm Tuần Tự luôn chậm. Thực ra, nếu mảng chỉ có vài phần tử, nó nhanh và đơn giản hơn nhiều so với việc sắp xếp mảng trước để dùng các thuật toán phức tạp.

Một số người cũng cho rằng Tìm Kiếm Tuần Tự vô dụng với mảng lớn. Điều này chỉ đúng khi bạn cần tối ưu hóa thời gian, nhưng đôi khi độ phức tạp thêm vào từ các thuật toán khác lại không đáng.

Không ít người cho rằng Tìm Kiếm Tuần Tự chỉ dành cho dữ liệu không sắp xếp. Thực tế, bạn vẫn có thể dùng nó cho mảng sắp xếp nếu điều kiện khác chưa đủ để chuyển sang thuật toán phức tạp hơn.

Điều cuối cùng, không nên cho rằng Tìm Kiếm Tuần Tự là thô sơ hay lỗi thời. Đôi khi, sự đơn giản và mộc mạc của nó lại là lựa chọn tối ưu.

Tóm Tắt

Tìm Kiếm Tuần Tự là một phương pháp đơn giản nhưng hiệu quả để tìm kiếm giá trị trong một mảng.

Nó đi qua từng phần tử của mảng và kiểm tra giá trị cho đến khi tìm thấy hoặc đến cuối mảng.

Độ phức tạp thời gian là O(n), và độ phức tạp không gian là O(1), phù hợp cho các mảng nhỏ hoặc dữ liệu chưa được sắp xếp.

Quan trọng hơn, nó đặt nền tảng cho những hiểu biết về thuật toán tìm kiếm, giúp bạn có cái nhìn sâu sắc hơn vào các phương pháp tìm kiếm trong lập trình.

Nguồn: Viễn Đinh - Cách Giải Tìm Kiếm Tuần Tự