Thuật toán tìm kiếm tuyến tính (Linear Search): Nguyên lý và Cài đặt

Trong khoa học máy tính, trước khi bàn về những kỹ thuật tối ưu hóa phức tạp, người làm nghề cần nắm vững những nền tảng cơ bản nhất. Linear Search (Tìm kiếm tuyến tính) chính là viên gạch đầu tiên đó. Phương pháp này giải quyết vấn đề một cách tự nhiên, trực quan và phản ánh chính xác tư duy tìm kiếm của con người trong đời sống thực. Bài viết này sẽ giúp bạn hiểu rõ bản chất, ưu nhược điểm và cách áp dụng giải thuật này vào thực tế lập trình.

Thuật toán tìm kiếm tuyến tính (Linear Search) là gì?

Linear Search là giải pháp tìm kiếm sơ khai và đơn giản nhất. Khác với Binary Search (Tìm kiếm nhị phân) đòi hỏi dữ liệu phải được sắp xếp trật tự, Linear Search hoạt động trên mọi tập dữ liệu, bất kể thứ tự.

Bản chất của thuật toán là thực hiện rà soát tuần tự. Máy tính sẽ kiểm tra lần lượt từng phần tử trong danh sách từ đầu đến cuối cho đến khi phát hiện giá trị cần tìm hoặc đã duyệt hết toàn bộ danh sách mà không có kết quả. Do tính chất duyệt tuần tự này, phương pháp còn được gọi là Sequential Search.

Nguyên lý hoạt động và độ phức tạp

Cơ chế vận hành của Linear Search rất trực diện: bắt đầu từ phần tử đầu tiên (index 0), so sánh phần tử đang xét với giá trị mục tiêu (target). Nếu trùng khớp, thuật toán trả về vị trí index và kết thúc. Nếu không, quá trình tiếp tục dịch chuyển sang phần tử kế tiếp.

Về độ phức tạp thời gian (Time Complexity):

Trường hợp tốt nhất (Best Case): Giá trị cần tìm nằm ngay vị trí đầu tiên của mảng. Lúc này, độ phức tạp là O(1).
Trường hợp xấu nhất (Worst Case): Giá trị mục tiêu nằm ở vị trí cuối cùng hoặc hoàn toàn không tồn tại trong mảng. Thuật toán buộc phải duyệt qua toàn bộ n phần tử. Độ phức tạp là O(n).
Trường hợp trung bình (Average Case): Về mặt thống kê, độ phức tạp vẫn là O(n).

Về độ phức tạp không gian (Space Complexity):

Giải thuật đạt hiệu quả cao về mặt không gian với độ phức tạp $O(1)$. Lý do là Linear Search chỉ sử dụng một vài biến tạm để lưu chỉ số và giá trị so sánh, không yêu cầu cấp phát thêm vùng nhớ phụ thuộc vào kích thước dữ liệu đầu vào.

Ví dụ minh họa và mô phỏng từng bước

Để hình dung rõ hơn, hãy xem xét bài toán cụ thể sau.

Cho mảng A = [10, 50, 30, 70, 80, 20] và giá trị cần tìm x \= 30.

Quá trình tìm kiếm sẽ diễn ra như sau:

Bước 1: Tại vị trí index 0. So sánh x với A[0] (30). Kết quả: Không khớp. Chuyển sang phần tử tiếp theo.
Bước 2: Tại vị trí index 1. So sánh x với A[1] (50). Kết quả: Không khớp. Chuyển tiếp.
Bước 3: Tại vị trí index 2. So sánh x với A[2] (30). Kết quả: Khớp.
Kết thúc: Thuật toán dừng lại và trả về chỉ số 2.

Nếu duyệt đến hết mảng (sau số 20) mà vẫn không tìm thấy 30, thuật toán sẽ trả về giá trị biểu thị không tìm thấy (thường là -1 hoặc null).

Mã giả (Pseudocode)

Dưới đây là logic thuật toán được trình bày dưới dạng mã giả, giúp bạn dễ dàng chuyển đổi sang bất kỳ ngôn ngữ lập trình nào như Python, Java, C++ hay Go.


Hàm LinearSearch(Mảng A, Giá trị x):
    Duyệt i từ 0 đến (độ dài của A - 1):
        Nếu A[i] bằng x:
            Trả về i (Đã tìm thấy tại vị trí i)
    Trả về -1 (Không tìm thấy giá trị x trong mảng)

Bài tập thực hành trên LeetCode

Tư duy "duyệt tuyến tính" là nền tảng cho rất nhiều bài toán xử lý mảng. Dưới đây là hai bài tập trên LeetCode giúp củng cố kỹ năng này.

1. Find Numbers with Even Number of Digits (LeetCode 1295)

Bài toán: Cho một mảng các số nguyên, hãy đếm xem có bao nhiêu số trong mảng sở hữu số lượng chữ số là số chẵn (ví dụ: số 12 có 2 chữ số -> chẵn).

Ứng dụng tư duy Linear Search:

Bạn cần duyệt qua từng phần tử của mảng (tương tự như Linear Search duyệt tìm giá trị). Tại mỗi phần tử, chúng ta thực hiện đếm số lượng chữ số. Biến đếm kết quả sẽ tăng lên nếu số lượng chữ số của phần tử đó là chẵn. Đây là ví dụ điển hình về việc duyệt tuyến tính để kiểm tra tính chất của dữ liệu thay vì chỉ tìm kiếm giá trị.

2. Richest Customer Wealth (LeetCode 1672)

Bài toán: Bạn được cung cấp một lưới m x n, đại diện cho tài khoản của các khách hàng tại các ngân hàng khác nhau. Hàng i đại diện cho một khách hàng, cột j là số tiền họ có tại ngân hàng đó. Nhiệm vụ là tìm ra khách hàng có tổng tài sản lớn nhất.

Ứng dụng tư duy Linear Search:

Bài toán này là sự kết hợp của việc duyệt mảng và tìm giá trị lớn nhất (Max Finding - một biến thể của Linear Search).

Duyệt qua từng hàng (từng khách hàng).
Với mỗi hàng, duyệt tuyến tính để tính tổng các phần tử con (tổng tiền).
So sánh tổng tiền vừa tính với giá trị lớn nhất hiện tại (max_wealth). Nếu lớn hơn, cập nhật max_wealth.

Linear Search tuy đơn giản nhưng lại là giải thuật có tính ứng dụng thực tế rất cao, đặc biệt khi làm việc với dữ liệu nhỏ hoặc chưa được sắp xếp. Việc hiểu sâu sắc về O(n) và cơ chế hoạt động của thuật toán này sẽ tạo tiền đề vững chắc để bạn tiếp cận các giải thuật tìm kiếm nâng cao hơn như Binary Search hay Interpolation Search. Hãy bắt đầu luyện tập ngay với các bài toán trên LeetCode để rèn giũa tư duy này!