Linear Search — Tìm kiếm tuyến tính

Nhiều kỹ sư coi thường Linear Search — "thuật toán trâu bò", "ai mà không biết". Nhưng đây chính xác là thuật toán tối ưu cho dữ liệu chưa sắp xếp. Mỗi lần database thực hiện full table scan, mỗi lần grep quét file, mỗi lần Array.prototype.find() trong JavaScript chạy — đó đều là linear search.

Điều thú vị hơn: với mảng nhỏ (n ≤ 64), linear search thường nhanh hơn binary search trên thực tế nhờ sequential memory access pattern. CPU prefetcher đoán trước dữ liệu cần đọc, trong khi binary search nhảy lung tung trong bộ nhớ khiến cache miss liên tục.

Hiểu khi nào linear search là lựa chọn đúng — và khi nào cần chuyển sang giải pháp khác — là dấu hiệu của một kỹ sư trưởng thành.

Bức tranh tư duy

Hình dung bạn cần tìm chìa khóa trong túi xách. Túi không có ngăn phân loại — bạn thò tay vào, lần lượt sờ từng vật: ví, son, điện thoại, tai nghe... cho đến khi chạm đúng chìa khóa. Không có cách nào nhanh hơn khi đồ trong túi không có thứ tự.

text

Mảng:  [7, 2, 9, 4, 1, 8, 3]     target = 4

Bước 1:  [7] 2  9  4  1  8  3    → 7 ≠ 4, tiếp
Bước 2:   7 [2] 9  4  1  8  3    → 2 ≠ 4, tiếp
Bước 3:   7  2 [9] 4  1  8  3    → 9 ≠ 4, tiếp
Bước 4:   7  2  9 [4] 1  8  3    → 4 == 4, TÌM THẤY tại index 3!

Nếu chìa khóa nằm ở đáy túi (cuối mảng), bạn phải kiểm tra hết mọi vật — đó là worst case O(n). Nếu may mắn nằm trên cùng — O(1). Trung bình, bạn kiểm tra khoảng n/2 vật.

📌 Khi nào analogy bị phá vỡ

Trong đời thực, bạn có thể nhận dạng chìa khóa bằng hình dạng/cảm giác mà không cần so sánh tuần tự. Máy tính không có "trực giác" đó — nó phải so sánh từng phần tử một cách tường minh.

Cốt lõi kỹ thuật

Cài đặt cơ bản

Ý tưởng đơn giản nhất: duyệt từ đầu đến cuối, so sánh từng phần tử với target.

C++PythonJavaGo

cpp

int linearSearch(const int arr[], int n, int target) {
    for (int i = 0; i < n; i++) {
        if (arr[i] == target)
            return i;
    }
    return -1;
}

python

def linear_search(arr: list[int], target: int) -> int:
    for i in range(len(arr)):
        if arr[i] == target:
            return i
    return -1

java

public static int linearSearch(int[] arr, int target) {
    for (int i = 0; i < arr.length; i++) {
        if (arr[i] == target)
            return i;
    }
    return -1;
}

func linearSearch(arr []int, target int) int {
    for i, v := range arr {
        if v == target {
            return i
        }
    }
    return -1
}

Mỗi vòng lặp thực hiện hai phép so sánh: i < n (kiểm tra biên) và arr[i] == target (kiểm tra giá trị). Với n phần tử, worst case cần 2n phép so sánh. Có cách giảm xuống n + 1 không? Có — sentinel search.

Sentinel Linear Search

Kỹ thuật sentinel loại bỏ phép kiểm tra biên bằng cách đặt target vào cuối mảng. Vòng lặp chắc chắn dừng — câu hỏi chỉ là dừng ở vị trí nào.

C++PythonJavaGo

cpp

int sentinelSearch(int arr[], int n, int target) {
    int last = arr[n - 1];
    arr[n - 1] = target;  // đặt sentinel

    int i = 0;
    while (arr[i] != target)
        i++;

    arr[n - 1] = last;  // khôi phục giá trị gốc

    if (i < n - 1 || arr[n - 1] == target)
        return i;
    return -1;
}

python

def sentinel_search(arr: list[int], target: int) -> int:
    n = len(arr)
    if n == 0:
        return -1

    last = arr[n - 1]
    arr[n - 1] = target  # đặt sentinel

    i = 0
    while arr[i] != target:
        i += 1

    arr[n - 1] = last  # khôi phục

    if i < n - 1 or arr[n - 1] == target:
        return i
    return -1

java

public static int sentinelSearch(int[] arr, int target) {
    int n = arr.length;
    if (n == 0) return -1;

    int last = arr[n - 1];
    arr[n - 1] = target;

    int i = 0;
    while (arr[i] != target)
        i++;

    arr[n - 1] = last;

    if (i < n - 1 || arr[n - 1] == target)
        return i;
    return -1;
}

func sentinelSearch(arr []int, target int) int {
    n := len(arr)
    if n == 0 {
        return -1
    }

    last := arr[n-1]
    arr[n-1] = target

    i := 0
    for arr[i] != target {
        i++
    }

    arr[n-1] = last

    if i < n-1 || arr[n-1] == target {
        return i
    }
    return -1
}

Sentinel giảm từ 2n xuống n + 1 phép so sánh — tiết kiệm ~50% branch instructions. Trên mảng lớn, điều này tạo ra sự khác biệt đo được.

Lưu ý quan trọng

Sentinel search thay đổi mảng gốc tạm thời — không an toàn trong môi trường multi-thread. Chỉ dùng khi bạn kiểm soát hoàn toàn quyền truy cập mảng.

Tìm kiếm trên Linked List

Linear search là thuật toán tìm kiếm duy nhất khả thi trên linked list, vì linked list không hỗ trợ random access.

C++PythonJavaGo

cpp

struct Node {
    int data;
    Node* next;
};

Node* linearSearchList(Node* head, int target) {
    Node* current = head;
    while (current != nullptr) {
        if (current->data == target)
            return current;
        current = current->next;
    }
    return nullptr;
}

python

class Node:
    def __init__(self, data: int):
        self.data = data
        self.next: Node | None = None

def search_linked_list(head: Node | None, target: int) -> Node | None:
    current = head
    while current is not None:
        if current.data == target:
            return current
        current = current.next
    return None

java

class Node {
    int data;
    Node next;
    Node(int data) { this.data = data; }
}

public static Node searchLinkedList(Node head, int target) {
    Node current = head;
    while (current != null) {
        if (current.data == target)
            return current;
        current = current.next;
    }
    return null;
}

type Node struct {
    Data int
    Next *Node
}

func searchLinkedList(head *Node, target int) *Node {
    current := head
    for current != nil {
        if current.Data == target {
            return current
        }
        current = current.Next
    }
    return nil
}

Thực chiến

Tình huống: Tìm kiếm trên streaming data

Bối cảnh: Hệ thống log monitoring nhận dòng log liên tục từ Kafka. Cần phát hiện log entry chứa pattern đáng ngờ (error code cụ thể) trong real-time. Dữ liệu không được sort và không thể buffer toàn bộ vào memory.

Mục tiêu: Scan từng batch log entries, trả về matches ngay lập tức.

python

from typing import Generator

def scan_log_stream(
    log_stream: Generator[str, None, None],
    error_codes: set[str],
    batch_size: int = 1000
) -> Generator[tuple[int, str], None, None]:
    """Scan streaming logs cho error codes — linear search là lựa chọn duy nhất."""
    line_number = 0

    for line in log_stream:
        line_number += 1
        # Linear scan qua set nhỏ error codes cho mỗi dòng
        for code in error_codes:
            if code in line:
                yield (line_number, line.strip())
                break  # tìm thấy 1 code là đủ, không cần scan tiếp

Phân tích:

Không thể sort streaming data → binary search không khả thi. Không thể hash toàn bộ stream → hash table không phù hợp cho matching pattern dạng substring. Linear scan từng dòng là giải pháp chính xác và hiệu quả nhất cho bài toán này. break khi tìm thấy code đầu tiên tránh scan dư thừa.

Tình huống: Tìm phần tử trong mảng nhỏ — khi linear thắng binary

Bối cảnh: Config parser cần kiểm tra xem một directive có nằm trong danh sách khoảng 20 valid directives không. Team cũ dùng binary search trên sorted array.

cpp

// Với n ≤ 20, linear search thắng binary search nhờ branch prediction
// và sequential memory access
bool isValidDirective(const std::string& directive,
                      const std::vector<std::string>& valid_directives) {
    for (const auto& d : valid_directives) {
        if (d == directive) return true;
    }
    return false;
}

Phân tích:

Với n = 20, binary search cần ~5 so sánh nhưng mỗi so sánh có thể cache miss. Linear search cần trung bình 10 so sánh nhưng CPU prefetcher load sẵn dữ liệu liên tiếp. Trên benchmarks thực tế, linear search trên mảng nhỏ thường nhanh hơn 20-40% so với binary search.

Sai lầm điển hình

❌ Sai lầm 1: Dùng binary search trên dữ liệu chưa sort

Vấn đề: Nghĩ rằng binary search "luôn nhanh hơn" nên dùng trên mảng chưa sắp xếp.

python

# SAI: binary search trên mảng chưa sort — kết quả sai hoàn toàn
arr = [7, 2, 9, 4, 1, 8, 3]
result = binary_search(arr, 4)  # có thể trả về -1 dù 4 có trong mảng!

Tại sao sai: Binary search giả định mảng đã sort. Khi mid trỏ đến giá trị lớn hơn target, nó loại bỏ nửa phải — nhưng target có thể nằm ở nửa phải nếu mảng chưa sort. Kết quả: âm thầm trả về sai, không có error. Đây là bug nguy hiểm vì nó không crash — chỉ cho kết quả wrong.

python

# ĐÚNG: kiểm tra precondition hoặc dùng linear search
arr = [7, 2, 9, 4, 1, 8, 3]
result = linear_search(arr, 4)  # luôn đúng, không cần sort

❌ Sai lầm 2: Bỏ qua linear search cho mảng nhỏ

Vấn đề: Luôn sort + binary search bất kể kích thước mảng.

python

# SAI: sort O(n log n) + binary search O(log n) cho mảng 10 phần tử
small_arr = [5, 3, 8, 1, 9, 2, 7, 4, 6, 10]
small_arr.sort()  # tốn O(n log n) — vô nghĩa cho n=10
binary_search(small_arr, 7)

Tại sao sai: Chi phí sort là O(n log n), lớn hơn nhiều so với linear search O(n). Nếu chỉ tìm một lần, tổng chi phí sort + binary search luôn thua linear search thuần. Chỉ sort khi bạn cần tìm nhiều lần trên cùng dữ liệu.

python

# ĐÚNG: linear search cho mảng nhỏ hoặc tìm một lần
small_arr = [5, 3, 8, 1, 9, 2, 7, 4, 6, 10]
linear_search(small_arr, 7)  # O(n) — đủ nhanh, không cần sort

❌ Sai lầm 3: Quên xử lý mảng rỗng

Vấn đề: Không kiểm tra edge case mảng rỗng, đặc biệt với sentinel search.

python

# SAI: sentinel search trên mảng rỗng → IndexError
def sentinel_search_buggy(arr, target):
    last = arr[len(arr) - 1]  # IndexError khi arr rỗng!
    # ...

Tại sao sai: Trong production, input không bao giờ "luôn hợp lệ". API có thể trả về mảng rỗng, database query có thể không có kết quả. Crash ở đây khiến toàn bộ request pipeline fail.

python

# ĐÚNG: guard clause cho mảng rỗng
def sentinel_search_safe(arr, target):
    if not arr:
        return -1
    last = arr[len(arr) - 1]
    # ...

Under the Hood

Hiệu năng

Case	Time	Số phép so sánh	Ghi chú
Best	O(1)	1	Target ở vị trí đầu tiên
Average	O(n)	n/2	Giả định phân bố đều
Worst	O(n)	n	Target ở cuối hoặc không tồn tại
Sentinel	O(n)	n + 1 (chỉ 1 so sánh/bước)	Giảm ~50% branch instructions

Space complexity: O(1) — không cần bộ nhớ phụ ngoài vài biến.

Memory access pattern

Linear search truy cập bộ nhớ tuần tự (sequential access). Đây là pattern thân thiện nhất với CPU cache hierarchy:

Cache line: CPU không đọc từng byte mà đọc theo cache line (thường 64 bytes = 16 int). Khi bạn truy cập arr[0], CPU tự động load luôn arr[1] đến arr[15] vào L1 cache. Các phép so sánh tiếp theo gần như miễn phí về mặt memory latency.

Branch prediction: Vòng lặp linear search có pattern cực kỳ dễ đoán — "tiếp tục" gần như mọi lần, chỉ "dừng" một lần duy nhất. CPU branch predictor đạt accuracy gần 100%.

Đây là lý do linear search trên mảng nhỏ thường nhanh hơn binary search — binary search nhảy ngẫu nhiên trong mảng, gây cache miss ở mỗi bước.

So sánh với hash table lookup

Tiêu chí	Linear Search	Hash Table
Time	O(n)	O(1) amortized
Space	O(1) thêm	O(n) thêm
Setup	Không cần	Cần xây hash table
Dữ liệu streaming	✅ Xử lý được	❌ Cần toàn bộ data
Dữ liệu thay đổi liên tục	✅ Không cần rebuild	⚠️ Cần update hash table

Hash table thắng tuyệt đối khi cần tìm nhiều lần trên dữ liệu tĩnh. Linear search thắng khi dữ liệu nhỏ, streaming, hoặc chỉ tìm một vài lần.

Checklist ghi nhớ

✅ Checklist triển khai

Cài đặt cơ bản

[ ] Viết được linear search cho array và linked list
[ ] Áp dụng sentinel optimization và hiểu trade-off (không thread-safe)
[ ] Luôn xử lý edge case mảng rỗng trước khi truy cập phần tử

Khi nào dùng linear search

[ ] Dữ liệu chưa sắp xếp — linear search là lựa chọn tối ưu
[ ] Mảng nhỏ (n ≤ 64) — cache locality thắng O(log n)
[ ] Streaming data — không thể sort hoặc index trước
[ ] Tìm kiếm chỉ thực hiện một vài lần — không đáng sort

Khi nào KHÔNG dùng

[ ] Mảng lớn đã sort và cần tìm nhiều lần → chuyển sang binary search
[ ] Cần lookup O(1) trên tập dữ liệu tĩnh → dùng hash table
[ ] Dữ liệu có cấu trúc cây → dùng tree search

Bài tập luyện tập

Bài 1: Đếm số lần xuất hiện — Foundation

Đề bài: Cho mảng arr và giá trị target, đếm số lần target xuất hiện trong mảng. Không được sort mảng.

Input: arr = [1, 3, 7, 3, 2, 3, 8], target = 3Output: 3

🧠 Quiz

Linear search có thể dùng cho dữ liệu nào?

[ ] A. Chỉ mảng đã sắp xếp
[ ] B. Chỉ mảng số nguyên
[x] C. Mọi cấu trúc dữ liệu iterable — sorted hoặc unsorted
[ ] D. Chỉ mảng có kích thước nhỏ hơn 1000 Giải thích: Linear search không yêu cầu bất kỳ tiền điều kiện nào về dữ liệu. Nó hoạt động trên mọi cấu trúc dữ liệu mà bạn có thể duyệt tuần tự — array, linked list, stream, file, v.v.

💡 Gợi ý

Không return ngay khi tìm thấy — phải duyệt hết mảng
Dùng biến đếm, tăng mỗi khi gặp target

✅ Lời giải

C++PythonJavaGo

cpp

int countOccurrences(const int arr[], int n, int target) {
    int count = 0;
    for (int i = 0; i < n; i++) {
        if (arr[i] == target)
            count++;
    }
    return count;
}

python

def count_occurrences(arr: list[int], target: int) -> int:
    count = 0
    for x in arr:
        if x == target:
            count += 1
    return count

java

public static int countOccurrences(int[] arr, int target) {
    int count = 0;
    for (int x : arr) {
        if (x == target) count++;
    }
    return count;
}

func countOccurrences(arr []int, target int) int {
    count := 0
    for _, v := range arr {
        if v == target {
            count++
        }
    }
    return count
}

Phân tích: Time O(n) — phải duyệt hết mảng dù tìm thấy sớm vì cần đếm tất cả. Space O(1).

Bài 2: Tìm hai phần tử có tổng bằng target — Intermediate

Đề bài: Cho mảng arr chưa sắp xếp và giá trị target. Tìm hai phần tử có tổng bằng target. Trả về index của chúng. Không được sort mảng.

Input: arr = [3, 7, 1, 9, 2], target = 10Output: (0, 3) (vì arr[0] + arr[3] = 3 + 7 = 10... sai, 3 + 9 = 12)

Chờ đã — arr[1] + arr[0] = 7 + 3 = 10 → Output: (0, 1)

🧠 Quiz

Sentinel search giảm số phép so sánh bằng cách nào?

[ ] A. Dùng binary search thay vì linear
[x] B. Loại bỏ phép kiểm tra biên mảng trong mỗi vòng lặp
[ ] C. Sort mảng trước khi tìm
[ ] D. Dùng hash table bên trong Giải thích: Sentinel đặt target vào cuối mảng, đảm bảo vòng lặp luôn dừng. Nhờ vậy, mỗi bước chỉ cần 1 phép so sánh (giá trị) thay vì 2 (biên + giá trị). Từ 2n xuống n + 1 phép so sánh.

💡 Gợi ý

Brute force: hai vòng lặp lồng nhau O(n²)
Tối ưu hơn: dùng hash set lưu các giá trị đã thấy → O(n)
Suy nghĩ: complement = target - arr[i], kiểm tra complement đã xuất hiện chưa

✅ Lời giải

python

def two_sum(arr: list[int], target: int) -> tuple[int, int] | None:
    seen = {}  # value → index
    for i, x in enumerate(arr):
        complement = target - x
        if complement in seen:
            return (seen[complement], i)
        seen[x] = i
    return None

Phân tích: Time O(n) — một lần duyệt. Space O(n) cho hash map. Đây là trade-off kinh điển: đánh đổi bộ nhớ lấy tốc độ, chuyển từ brute force O(n²) xuống O(n). Bài toán Two Sum này là câu phỏng vấn #1 trên LeetCode.

Liên kết học tiếp

Từ khóa glossary: Linear Search, Sequential Search, Sentinel Search, brute force, cache locality, full table scan

Tìm kiếm liên quan: tìm kiếm tuyến tính, tìm kiếm tuần tự, duyệt mảng, sequential scan

Linear Search — Tìm kiếm tuyến tính ​

Bức tranh tư duy ​

Cốt lõi kỹ thuật ​

Cài đặt cơ bản ​

Sentinel Linear Search ​

Tìm kiếm trên Linked List ​

Thực chiến ​

Tình huống: Tìm kiếm trên streaming data ​

Tình huống: Tìm phần tử trong mảng nhỏ — khi linear thắng binary ​

Sai lầm điển hình ​

❌ Sai lầm 1: Dùng binary search trên dữ liệu chưa sort ​

❌ Sai lầm 2: Bỏ qua linear search cho mảng nhỏ ​

❌ Sai lầm 3: Quên xử lý mảng rỗng ​

Under the Hood ​

Hiệu năng ​

Memory access pattern ​

So sánh với hash table lookup ​

Checklist ghi nhớ ​

Bài tập luyện tập ​

Bài 1: Đếm số lần xuất hiện — Foundation ​

Bài 2: Tìm hai phần tử có tổng bằng target — Intermediate ​

Liên kết học tiếp ​

Linear Search — Tìm kiếm tuyến tính

Bức tranh tư duy

Cốt lõi kỹ thuật

Cài đặt cơ bản

Sentinel Linear Search

Tìm kiếm trên Linked List

Thực chiến

Tình huống: Tìm kiếm trên streaming data

Tình huống: Tìm phần tử trong mảng nhỏ — khi linear thắng binary

Sai lầm điển hình

❌ Sai lầm 1: Dùng binary search trên dữ liệu chưa sort

❌ Sai lầm 2: Bỏ qua linear search cho mảng nhỏ

❌ Sai lầm 3: Quên xử lý mảng rỗng

Under the Hood

Hiệu năng

Memory access pattern

So sánh với hash table lookup

Checklist ghi nhớ

Bài tập luyện tập

Bài 1: Đếm số lần xuất hiện — Foundation

Bài 2: Tìm hai phần tử có tổng bằng target — Intermediate

Liên kết học tiếp