Linear Search (Tìm Kiếm Tuyến Tính)

Đây là thuật toán tìm kiếm đơn giản nhất ("trâu bò" nhất).

Cơ Chế

Duyệt qua từng phần tử của mảng, từ đầu đến cuối. Nếu gặp phần tử cần tìm thì trả về vị trí của nó. Nếu đi hết mảng mà không thấy thì trả về -1.

Code Implementation

C++

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

Java

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

Python

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

Đánh Giá

• Ưu điểm: Dễ cài đặt, không cần mảng phải sắp xếp trước.
• Nhược điểm: Chậm (O(N)). Nếu mảng có 1 tỷ phần tử, nó phải so sánh 1 tỷ lần trong trường hợp xấu nhất.